백준 2531번 : 회전초밥 [Java]
문제
https://www.acmicpc.net/problem/2531
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_2531 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); //접시 수
int d = Integer.parseInt(st.nextToken()); //초밥 종류
int k = Integer.parseInt(st.nextToken()); //연속으로 몇개 먹는지
int c = Integer.parseInt(st.nextToken()); //쿠폰의 수
int[] sushi = new int[n];
for(int i = 0; i < n; i++) {
sushi[i] = Integer.parseInt(br.readLine());
}
boolean[] eatCheck = new boolean[d + 1];
int answer = -1;
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < k; j++) {
if(!eatCheck[sushi[(i + j) % n]]) {
eatCheck[sushi[(i + j) % n]] = true;
count++;
}
}
if(!eatCheck[c]) {
answer = Math.max(answer, count + 1);
}
answer = Math.max(answer, count);
eatCheck[sushi[i]] = false;
count--;
}
System.out.println(answer);
}
}
접근 방법
초밥 가짓수인 d만큼 check할 boolean배열을 만든다.
초밥 배열을 순차적으로 탐색하면서 해당 접시를 첫번째로 먹는다고 가정한다.
배열 크기가 넘어가는 것을 고려해서 i + j % n으로 인덱스 계산을 해준다.
먹은 접시를 true로 바꿔준다.
true인 개수를 세고 false로 바꾸면서 만약 쿠폰부분이 false라면 개수 + 1을 해서 최대값을 찾는다.
시행 착오
true인 개수를 세는 행위가 시간이 오래 걸릴 것 같아서
어차피 한칸식 슬라이딩 윈도우처럼 미는 형태이기 때문에 첫번째 접시 부분을 제외한 n -1개는 변하지 않는 다는 점을 이용하기로 했다.
그럼 첫번째 접시만 false로 변경해주고 count를 1감소 시킨다.
개수를 셀 때는 false -> true인 경우만 count를 증가하는 식으로 계산했다.
쿠폰 부분이 false일 때 count를 1증가 해주는 방향으로 했더니 테케 1번에서 count가 계속해서 증가하는 현상이 발생했다.
쿠폰을 사용할 수 있는 경우라면 +1을 한 뒤 break를 해주었다.
이렇게 할 경우 또 하나의 반례를 마주한게
어떤 상태에서 쿠폰을 사용할 수 있는 첫번째 경우가 반드시 최대값이 아닐 수도 있다는 사실을 놓쳤다.
그래서 위와 같이 코드를 고쳐주었고 해결되었다.
'문제풀이 > 코딩테스트' 카테고리의 다른 글
프로그래머스 디스크 컨트롤러 [Java] (0) | 2024.06.26 |
---|---|
소프티어 [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길 [Java] (0) | 2024.06.26 |
백준 1854번 : K번째 최단경로 찾기 [Java] (0) | 2024.03.03 |
백준 3197번 : 백조의 호수 [Java] (1) | 2024.03.02 |
백준 1916 : 최소비용 구하기 [Java] (0) | 2024.03.02 |