[백준] 2531번 - 회전 초밥(JAVA)

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

2531번: 회전 초밥

- 문제 -

---

- 풀이 과정 -

문제를 다시 풀어서 쉽게 말하자면 결국 연속된 숫자 중 중복되지 않은 숫자가 가장 많은 범위를 찾아 그 개수를 구하면 되는 문제입니다.

 

단, 쿠폰으로 추가 초밥을 먹을 수 있다는 점을 유의해야 합니다. 연속된 숫자 범위에서 쿠폰으로 먹을 수 있는 초밥이 없으면 카운트를 +1해줘야 합니다.

 

연속된 숫자의 범위에서 답을 구하는 문제인 만큼 sliding window기법을 사용하여 풀어줄 수 있습니다.

window의 범위를 옮기면서 범위 내의 숫자의 개수를 체크해주면 되며 window의 범위는 문제에 제시된 k만큼 지정합니다.

 

window범위 내의 숫자의 개수를 세기위해 지정할 수 있는 범위의 숫자(1~30)만큼 배열을 하나 생성하여 체크해 줍니다.

…..

 

window 범위를 옮기다 보면 쿠폰이 포함되지 않은 범위가 나옵니다. 

문제에서 연속된 초밥을 먹고 쿠폰으로 먹을 수 있는 초밥이 포함되지 않았다면 하나 더 먹을 수 있다고 되어있는 부분이 나온 것입니다.

그렇기에 카운트를 +1을 해주어 쿠폰으로 먹을 수 있는 초밥을 포함시켜 줍니다.

…..

 

이런식으로 window의 범위를 옮겨가면서 window의 시작부분(start)이 마지막에 도달할 때까지 숫자의 개수를 체크합니다.

 

이때 window의 끝 부분(end)이 마지막에 도달한 경우 다시 처음부터 시작되도록 해야 합니다. (코드 상으로는 배열이지만 실제로는 벨트 형태로 구성되어야 하기 때문입니다.)

즉, window 끝 부분이 배열의 끝인 N의 범위를 넘어가게 되면 처음으로 돌아가도록 해야 하기에 코드에서 %N을 적용하였습니다.

 

window의 시작 부분이 배열의 마지막 부분까지 이동해 모든 범위의 체크가 완료되었다면 카운트가 가장 높았던 수를 출력해주면 됩니다.

---

- 소스 코드 -

package com.test;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    //2531번 - 회전 초밥
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N,d,k,c;
    static int[] arr, eated;
    
    public static void main(String[] args) throws IOException{
        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()); // 쿠폰 번호
        
        arr=new int[N]; // 접시 갯수 만큼 생성
        eated=new int[d+1]; // index 1부터 사용하기 위해 초밥 갯수+1 만큼 생성
        
        for(int i=0;i<N;i++) {
            arr[i]=Integer.parseInt(br.readLine());
        }
        System.out.println(rotate());
    }
    
    public static int rotate() {
        int count=0,max=0;
        
        // 처음 window범위의 숫자 개수 카운트
        for(int i=0;i<k;i++) {
            if(eated[arr[i]]==0) count++;           
            eated[arr[i]]++;
        }
        
        // 쿠폰 번호가 포함된 초밥이 없는 경우 count증가 
        if(eated[c]==0) count++;
        eated[c]++;         
        max=count;
        
        for(int i=1;i<N;i++) {          
            //window start 지점
            eated[arr[i-1]]--;
            if(eated[arr[i-1]]==0) count--;
            
            //window end 지점
            eated[arr[(i+k-1)%N]]++;
            if(eated[arr[(i+k-1)%N]]==1) count++;
            
            if(max<count) max=count;
        }
        return max;
    }
}

 

[참고 사이트]

사이트

https://pangtrue.tistory.com/278