[BOJ] 백준 2531. 회전초밥 (+15961. 회전초밥)

문제

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

2531번: 회전 초밥

---

풀이

 슬라이딩 윈도우 문제입니다. N의 input size가 30,000이기 때문에 for 문을 2번 돌게 되면 시간 제한 1초를 넘기게 됩니다. 

 

 관건은 초밥의 개수가 아닌 종류를 세야하는 것인데, 이는 Map 자료형을 통해 해결했습니다. map에서 key를 초밥의 종류로, value를 종류 당 개수로 지정해주고, 종류 카운트는 map.size를 통해 세어주었습니다. 여기서 만약 value가 0이라면 map에서 제거했습니다.

 

 그리고 배열의 크기를 N+k-1의 크기로 지정해주어, 회전하는 배열을 구현했습니다. 회전 배열임으로, N에서부터 스시를 선택하면 다시 돌아와 k-1만큼 더한 값만큼을 고려해주어야 하기 때문입니다.

 

아래는 해당 풀이입니다.

---

소스코드

import java.util.*;

public class B2531_회전초밥 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int d = sc.nextInt();
        int k = sc.nextInt();
        int c = sc.nextInt();
        int[] sushis = new int[N+k-1];

        for(int i = 0;i<N;i++){
            sushis[i] = sc.nextInt();
        }
        for(int i = N;i<N+k-1;i++){
            sushis[i] = sushis[i-N]; // 회전배열 필요값만큼만 정의
        }

        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<k;i++){
            map.put(sushis[i], map.getOrDefault(sushis[i],0)+1);
        }
        map.put(c, map.getOrDefault(c,0)+1);
        int max = map.size();

        for(int ed=k;ed<N+k-1;ed++){
            int cnt;
            int st = ed-k;
            int out = sushis[st];
            
			//1. 나가는 초밥 빼기
            map.put(out,map.get(out)-1); 
            if(map.get(out)==0) map.remove(out); //나가는 초밥이 만약 0이면 map에서 제외
			
            //2. 추가된 초밥 넣기
            int in = sushis[ed];
            map.put(in, map.getOrDefault(in,0)+1); 
            
            //3. 쿠폰 번호 넣기
            map.put(c, map.getOrDefault(c,0)+1); 

            cnt = map.size();
            max = Math.max(cnt, max);

        }
        System.out.println(max);
    }
}

 

 

 

---

+

위 풀이를 아래 문제에도 똑같이 적용해 해결할 수 있습니다. 

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

15961번: 회전 초밥