[백준] 2531번 회전 초밥 (자바 풀이)

문제

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

2531번: 회전 초밥

 

풀이

이 문제는 투 포인터 문제이다. 그냥 모든 경우의 수를 다 보면 O(N^2)으로 시간초과가 발생한다. 투 포인터 방식을 사용하면 O(N)에 문제를 해결할 수 있다. 나는 슬라이딩 윈도우 방식처럼 투 포인터를 사용하고 HashMap을 사용하여 해결하였다.

 

예를 들어

8 30 4 30
7
9
7
30
2
7
9
25

위와 같은 예제는.

{7,9,7,30} -> HashMap[초밥 종류(key), 개수(value)]에 저장 -> { [7,2], [9,1], [30,1] } -> 쿠폰 초밥 30 이미 있음

-> 최대 3종류(size = 3)

이렇게 초기 세팅을 하고, 왼쪽 초밥을 하나 빼고 오른쪽 초밥을 하나 넣으면서 탐색하면 된다.

 

{9,7,30,2} -> { [9,1], [7,1], [30,1], [2,1] } ->  쿠폰 초밥 30 이미 있음 -> 최대 4종류(size = 4)

 

이때, 회전 초밥이므로 마지막 부분의 조합을 신경써야한다. 

 

이것은 앞쪽의 초밥 k-1개를 뒤에 붙여넣어 놓으면 된다.

7
9
7
30
2
7
9
25
7 <- 앞의 3개 붙여넣어놓기
9
7

이렇게 하면 {25,7,9,7} 까지 모든 조합을 살펴 볼 수 있다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Baekjoon_2531 {
    static int N,d,k,c;
    static int sushi[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        sushi = new int[N+k-1];
        for(int i=0; i<N; i++) {
            sushi[i] = Integer.parseInt(br.readLine());
        }
        
        for(int i=N; i<N+k-1; i++) {
            sushi[i] = sushi[i-N];
        }
            
        int ans = 0;
        HashMap<Integer, Integer> eat = new HashMap<>();
        
        /* 첫 k개 초밥 저장 */
        for(int i=0; i<k; i++) {
            eat.compute(sushi[i], (k,v) -> v==null ? 1 : v+1);
        }
        if(!eat.containsKey(c)) {    // 쿠폰 초밥이 없으면 +1
            ans = eat.size()+1;
        }else ans = eat.size();
        
        /* 슬라이딩 윈도우 탐색 */
        for(int i=0; i<N-1; i++) {
            if(eat.get(sushi[i]) == 1) {    // 하나 남으면 삭제
                eat.remove(sushi[i]);
            }else {    // 아니면 -1
                eat.put(sushi[i], eat.get(sushi[i])-1); 
            }
            // 오른쪽 것 추가
            eat.compute(sushi[i+k], (k,v) -> v==null ? 1 : v+1);
            
            if(!eat.containsKey(c)) {    // 쿠폰 초밥이 없으면 +1
                ans = Math.max(ans, eat.size()+1);
            }else {
                ans = Math.max(ans, eat.size());
            }
        }
        
        System.out.println(ans);
    }
}