[BOJ] 15961번. 회전초밥 - JAVA

🌱 문제 링크

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

15961번: 회전 초밥

 

📝 풀이 과정

문제 유형 : 슬라이딩 윈도우

 

처음에는 K개씩 끊어서 일일이 갯수를 셌는데 역시나 시간초과가 났다. 그러다 슬라이딩 윈도우 방식으로 풀어야 시간초과가 나지 않는다는 것을 알게 되었다. 

 

슬라이딩 윈도우

 

예를 들어 ABCDEF 가 있고 K가 3이라면,

S1 = A+B+C, S2 = B+C+D,  ....

이런식으로 구하지 않고, B와 C는 중복되므로 S2를 구할 때 앞에서 구한 S1에서 A를 뺴고 새로운 D를 넣어 구하는 방식이다. 마치 창문처럼 이동하면서 구간 합을 구할 수 있는 간단한 알고리즘이다. 

 

이것을 사용해서 코드를 짰다.

• 우선 처음 K개의 초밥들의 종류의 갯수를 센다.
  • count 배열에 현재 초밥(ex. 6번) 의 갯수가 0이라면 초밥의 종류(cnt)를 1 증가시키고 count 배열에도 1 증가시킨다.
• 두 번째 초밥부터 마지막 초밥까지 슬라이딩 윈도우를 사용하는데, 이전의 초밥을 빼고 새로운 초밥을 추가한다.
  • 이전 초밥을 count 배열에서 뺸 후 0이 된다면 초밥의 종류의 갯수도 1 감소한다.
  • 새로 추가되는 초밥의 갯수를 처음과 마찬가지로 1 증가시키는데, 증가시키기 전의 갯수가 0이라면 초밥의 종류의 갯수를 1 증가시킨다.
• max 값을 cnt의 최댓값으로 갱신한다.

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Main_bj_15961_회전초밥 {
    
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input_bj_15961.txt"));
        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[] dishes = new int[N];
        for(int i=0; i<N; i++) {
            dishes[i] = Integer.parseInt(br.readLine());
        }
        
        int[] count = new int[D+1];    // D 종류의 초밥 갯수를 셀 배열
        count[C]++;    // 쿠폰 추가
        int cnt=1;        // 초밥의 종류
        for(int i=0; i<K; i++) {
            if(count[dishes[i]]++ == 0) cnt++;
        }
        
        int max = cnt;
        for(int i=1; i<N; i++) {
            // i-1 번째 빼기
            if(--count[dishes[i-1]] == 0) cnt--;
            // i+K 번째 넣기 
            if(count[dishes[(i+K-1)%N]]++ == 0) cnt++;
            max = Math.max(max, cnt);
        }
        
        System.out.println(max);
        br.close();
    }
 
}
 

 

+) 덤으로 슬라이딩 윈도우 찾아보다 투 포인터도 알게 되었다.

투 포인터

투 포인터 알고리즘이란 2개의 포인터를 조작해서 원하는 것을 얻는 알고리즘을 뜻한다.

예를 들어, 위의 배열에서 요소들의 합이 10을 넘지 않는 부분 배열의 최대 길이를 구하는 문제가 있다고 하면,

 

두 개의 포인터 사이에 있는 요소들의 합이 10 이하인 경우의 포인터 간 거리를 구하면 될 것이다. 풀이 코드는 다음과 같다.

1) 투 포인터를 각각 left와 right로 선언한다. 처음에는 left와 right는 배열의 맨 앞에 존재한다.

2) 현재까지의 합이 10보다 작거나 같으면 길이를 재서 값을 갱신해 준다. 이후 right 포인터를 한 칸 오른쪽으로 이동시킨다.

3) 현재까지의 합이 10보다 크다면 left 포인터를 한 칸 오른쪽으로 이동시킨다.

​

위의 코드 기준으로는 [left, right) 범위의 값을 temp에 저장해서 사용한다. 위의 코드는 right가 배열의 끝에 도달하면 종료되도록 했지만 left가 배열의 끝에 도달할 때까지 반복해도 상관없다. (해당 문제의 경우는 최장거리를 구하는 문제여서 필요 없다고 판단해서 반복문 조건을 위와 같이 설정하였다. 문제에 따라서 유연하게 작성할 수 있도록 하자.)

[출처]슬라이딩 윈도우와 투 포인터|작성자 너와 

 

📌 채점 결과