[BOJ-15961][슬라이딩 윈도우] 회전 초밥 - Java

문제 바로가기

15961번: 회전 초밥

 

먹을 수 있는 초밥의 가짓수의 최댓값을 구하는 문제입니다.

초밥 개수가 최대 300만개이기 때문에 무식하게 N^2 하면 난리가 납니다.

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

public class Main{
    public static int solve(int[] sushi, int[] s, int k, int c) {
        int answer = 0;
        int cnt = 1;
        s[c]++;
        for(int i = 0; i < k; i++) {
            if(s[sushi[i]] == 0) cnt++;
            s[sushi[i]]++;
        }

        for(int i = 0; i < sushi.length; i++) {
            if(s[sushi[(i+k) % sushi.length]] == 0) cnt++;
            s[sushi[(i+k) % sushi.length]]++;

            s[sushi[i]]--;
            if(s[sushi[i]] == 0) cnt--;
            answer = Math.max(answer, cnt);
        }
        return answer;
    }

    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()); Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken());
        int[] s = new int[3001];
        int[] sushi = new int[N];

        for(int i = 0 ; i < N; i++) sushi[i] = Integer.parseInt(br.readLine());
        System.out.println(solve(sushi, s, k, c));
    }
}

일단 행사는 다 참여하여 초밥을 먹는다고 칩시다.

K개의 연속된 접시를 먹기 때문에 첫번째로 먹을 수 있는 초밥들과 그 다음 먹을 수 있는 초밥들은 K-1개가 항상 겹치게 됩니다.

따라서 맨 앞에꺼 하나 빼고 맨 뒤에꺼 하나 넣고 이런 식으로 체크해주면 O(N)으로 해결이 되는거져.

 

s[i] 배열은 i번 초밥이 포함된 개수이고,

cnt 는 초밥 가짓수의 개수입니다.

 

그리고 회전초밥이니깐 (i+k) % sushi.length 인덱스를 사용하는 것을 잊지 맙시다!

 

 

사실 슬라이딩 윈도우가 뭔지 잘 모릅니다 ㅎㅎ;; 

찾아보니 이런 방식이 창문 슥슥 미는 것과 같아서 슬라이딩 윈도우 방식이라고 부른다고 하네유 ^.^;;

 

 

감사합니다~~