[백준 15961번 / Java] BOJ 15961 : 회전 초밥(슬라이딩 윈도우, 원형 배열)

 

설계 시간: 10분

풀이 시간: 32분

디버깅 시간: 20분

 

15961번: 회전 초밥

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
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[] sushi = new int[N];
        for(int i = 0; i < N; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }

        Map<Integer, Integer> map = new HashMap<>();
        map.put(c, 1);
        for(int i = 0; i < k; i++) {
            map.put(sushi[i], map.getOrDefault(sushi[i], 0) + 1);
        }
        int max = map.size();
        for(int i = k; i < N + k; i++) {
            map.put(sushi[i % N], map.getOrDefault(sushi[i % N], 0) + 1);
            map.put(sushi[(i - k) % N], map.getOrDefault(sushi[(i - k) % N], 0) - 1);
            if(map.get(sushi[i - k]) == 0) {
                map.remove(sushi[i - k]);
            }
            max = Math.max(max, map.size());
        }
        System.out.println(max);
    }
}

 

느낀 점 및 정리 ✍️

1. 처음 설계했을 땐 "회전"(배열의 시작과 끝이 이어져있음)의 특성을 고려하지 않아서 제출 후 10퍼센트 정도에서 틀렸다는 문구가 출력됐었다. 슬라이딩 윈도우 알고리즘을 사용해서 Sysout으로 한 문장씩 아무리 찍어봐도 왜 틀린건지 알 수가 없었는데, 생각해보니 N번만 돌릴게 아니라 N + k - 1까지 돌려서 확인해야했다. 

2. 배열의 인덱스를 계산할 때, 크기를 넘어가지 않도록 i % N 을 사용하여 배열의 시작으로 다시 돌아오도록 작성했다.

3. 설계할 때부터 회전을 고려하지 못했어서 ㅠ ,, 이건 많은 문제들을 접하다보면 자연스럽게 고려하게 되겠지.. 싶다...! 파이팅