[CLASS 3: 슬라이딩윈도우] 백준 30804 과일 탕후루

30804번: 과일 탕후루

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

 

# 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 과일 배열 초기화
        int[] fruit = new int[n]; // 과일 정보를 저장하는 배열
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            fruit[i] = Integer.parseInt(st.nextToken());
        }

        // 슬라이딩 윈도우 알고리즘 초기화
        int[] count = new int[10]; // 각 과일(1~9번)의 개수를 저장하는 배열
        int start = 0;             // 현재 슬라이딩 윈도우의 시작점
        int end = 0;               // 현재 슬라이딩 윈도우의 끝점
        int maxLength = 0;         // 과일 종류가 2개 이하인 구간의 최대 길이
        int distinctCount = 0;     // 현재 윈도우 내의 과일 종류 개수

        // 슬라이딩 윈도우 탐색 시작
        while (end < n) {
            // 1. 윈도우의 끝점에 과일 추가
            if (count[fruit[end]] == 0) {
                // 새로운 과일을 추가하는 경우 (종류 개수 증가)
                distinctCount++;
            }
            count[fruit[end]]++; // 해당 과일 개수 증가
            end++; // 윈도우 끝점을 한 칸 확장

            // 2. 윈도우 내 과일 종류가 2개를 초과하면 윈도우 시작점 이동
            while (distinctCount > 2) {
                count[fruit[start]]--; // 윈도우 시작점의 과일 개수 감소
                if (count[fruit[start]] == 0) {
                    // 과일 종류가 0이 되면 종류 개수 감소
                    distinctCount--;
                }
                start++; // 윈도우 시작점을 한 칸 이동
            }

            // 3. 현재 윈도우의 크기를 계산하여 최대 길이 갱신
            // 현재 윈도우의 길이는 (end - start)
            maxLength = Math.max(maxLength, end - start);
        }

        // 결과 출력: 과일 종류가 2개 이하인 최대 길이
        System.out.println(maxLength);

        br.close();
    }
}

1. 입력 처리
   입력된 과일 개수와 배열을 저장한다. 배열의 각 원소는 과일 번호(1~9)이다.
2. 슬라이딩 윈도우 알고리즘 적용
   슬라이딩 윈도우 기법을 통해 배열의 시작점(start)과 끝점(end)을 조정하며, 조건에 맞는 최대 길이를 찾는다.
3. 윈도우 확장 (끝점 이동)
   • 끝점(end)을 오른쪽으로 이동하며, 현재 위치의 과일 번호를 추가한다.
   • 추가된 과일이 새롭게 등장하는 과일이면, 종류 개수(distinctCount)를 증가시킨다.
4. 윈도우 축소 (시작점 이동)
   • 만약 윈도우 내 과일 종류가 2개를 초과하면, 시작점(start)을 오른쪽으로 이동시켜 과일을 제거한다.
   • 과일 개수가 0이 되면 해당 과일은 윈도우에서 제외되므로, 종류 개수(distinctCount)를 감소시킨다.
5. 최대 길이 갱신
   • 매 단계에서 현재 윈도우의 길이 (end - start)를 계산하여 최대 길이(maxLength)를 갱신한다.
6. 결과 출력
   최종적으로 계산된 최대 길이를 출력한다.

 

 

시간 복잡도 분석

• 배열을 단 한 번 순회하며 시작점(start)과 끝점(end)을 조정하므로, 시간 복잡도는 O(N)이다.
• 배열의 크기가 최대 200,000200,000200,000까지 주어져도 효율적으로 동작한다.

 

 

핵심 포인트

1. 슬라이딩 윈도우 활용
   • 배열에서 연속된 구간을 탐색하면서 시작점과 끝점을 조정하여 조건을 만족하도록 한다.
   • 조건이 깨질 경우, 시작점을 이동시켜 윈도우를 축소한다.
2. 정확한 조건 구현
   • 과일 종류가 2개를 초과하는 경우만 윈도우를 축소한다.
   • 각 과일 번호의 개수를 관리하는 배열을 활용하여 효율적으로 구현한다.