[백준 BOJ/Gold IV] 15961번 : 회전 초밥

 

https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

 

이전에 풀었던 ↓ 이 문제랑 같은 문제인데 범위가 훨씬 더 큰 15961번!

 

https://fruits2lim.tistory.com/entry/%EB%B0%B1%EC%A4%80-BOJSilver-I-1940%EB%B2%88-%ED%9A%8C%EC%A0%84-%EC%B4%88%EB%B0%A5

[백준 BOJ/Silver I] 2531번 : 회전 초밥

 

투포인터 알고리즘을 이용하면 좋은데 범위가 고정된 경우 슬라이딩 윈도우 알고리즘으로 풀 수 있다!!

 

 

- 회전초밥이라 마지막 인덱스도 k개만큼 짝지어질 수 있기 때문에 길이를 늘려주었다  

        for(int i = 0; i < N; i++) {
            belt[i] = Integer.parseInt(br.readLine());
        }
        int index = 0;
        for(int i = N; i < N+k-1; i++) {
            belt[i] = belt[index];
            index++;
        }

 

 

- 0에서부터 k개만큼 담으면서 sushi 배열에 해당 번호가 담기는 경우 +1씩 해주는데 만약 값이 0이라면 이전에 들어간 번호가 아니기 때문에 count++ 해준다 (중복을 제외한 초밥 수를 세어야함)

        for(int i = 0; i < k; i++) {
            if(sushi[belt[i]] == 0) {
                count++; // 겹친 번호 없으면 count
            }
            sushi[belt[i]]++; // 먹은 번호 +1
        }

 

 

- 시작인덱스와 끝인덱스를 +1씩해서 이동해주며(시작에서 끝까지의 범위는 k) 전체 인덱스를 검사해주고, 시작인덱스가 N이 되면 끝까지 다 검사했다는거니까 while문을 빠져나온다

 

- 이동해줄때 start++ 가 되면 start-1번째에 있던 초밥은 빠지는데 이때 sushi에서의 값이 1이라면 딱 한번만 포함되어있던거니까 start-1이 제외되면서 count에서 1을 빼준다

- end++ 가 되면 end번째 초밥이 포함되는데 sushi에서의 값이 0이라면 새로운 초밥이 포함되는거니까 count에 1을 더해준다

            if(sushi[belt[start-1]] == 1) {
                count--; // 1이었다면 한번만 포함됐던거니까 빠지면서 count를 뺴줘야함
            }
            sushi[belt[start-1]]--;

            if(sushi[belt[end]] == 0) {
                count++; // 새로 포함되는 번호인데 그전에 포함된 번호 아니면 count
            }
            sushi[belt[end]]++;

 

 

- 초밥 c가 포함되어있지않다면 count에 1을 더해서 max값을 판단해준다

            if(sushi[c] == 0) {
                max = Math.max(max, count + 1); // c 포함 안되어있으면 +1
            } else {
                max = Math.max(max, count);
            }

 

 

 

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    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[] belt = new int[N+k-1]; // 회전 초밥인걸 생각해서 마지막 인덱스도 k개만큼 짝 지을 수 있도록 더 늘려줌
        int[] sushi = new int[d+1]; // 먹은 초밥 표시
        int count = 0; // 안 겹치는 초밥 개수

        for(int i = 0; i < N; i++) {
            belt[i] = Integer.parseInt(br.readLine());
        }
        int index = 0;
        for(int i = N; i < N+k-1; i++) {
            belt[i] = belt[index];
            index++;
        }


        for(int i = 0; i < k; i++) {
            if(sushi[belt[i]] == 0) {
                count++; // 겹친 번호 없으면 count
            }
            sushi[belt[i]]++; // 먹은 번호 +1
        }

        int max = count;
        int start = 0;
        int end = k-1;

        while(true) {
            start++;
            end++;

            if(start == N) break; // 끝까지 확인하면 break

            if(sushi[belt[start-1]] == 1) {
                count--; // 1이었다면 한번만 포함됐던거니까 빠지면서 count를 뺴줘야함
            }
            sushi[belt[start-1]]--;

            if(sushi[belt[end]] == 0) {
                count++; // 새로 포함되는 번호인데 그전에 포함된 번호 아니면 count
            }
            sushi[belt[end]]++;


            if(sushi[c] == 0) {
                max = Math.max(max, count + 1); // c 포함 안되어있으면 +1
            } else {
                max = Math.max(max, count);
            }
        }

        System.out.println(max);

    }

}