[백준 30804] 과일 탕후루 (Java)

이 문제는 막대에 꽂혀있는 과일들이 주어졌을 때, 앞과 뒤에서 임의의 개수만큼 제거하여 막대에 꽂혀있는 과일의 개수가 2개 이하가 되는 경우 중, 과일의 최대 개수를 구하는 문제이다.

처음에는 앞과 뒤에서 과일을 제거한다길래, Deque을 생각했는데 이 경우 문제가 너무 어려워졌다.

앞과 뒤에서 각각 몇개를 제거해야 막대에 있는 과일이 2종류 이하가 되는지도 모르는 상황에서 최댓값을 구하는 건 너무 복잡하기 때문이다.

따라서, 가장 쉬운 방법은 가능한 모든 경우를 확인해 보는 것이다. 이를 위해, 막대의 시작과 끝을 가리키는 각각의 포인터i, j를 도입하기로 결정했다.

먼저 아무것도 없는 초기 상태를 i = 0, j = -1이라 두고, currentKind를 0이라 두었다.

이 때, j를 이동시켜 과일 한 개를 막대에 꽂는다. 그리고, 막대에 있는 과일의 종류가 2종류 이상인 경우 막대에서 과일을 제거한다.

이후, 현재 막대에 꽂혀있는 과일의 개수를 센 뒤, 최대값을 갱신하면 문제가 해결된다.

이를 코드로 구현하면 다음과 같다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[] fruits = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < fruits.length; i++) {
            fruits[i] = Integer.parseInt(st.nextToken());
        }
        
        int i = 0, j = -1, max = 0, currentKind = 0;
        Map<Integer, Integer> count = new HashMap<>();
        while (j < fruits.length - 1) {
            j++;
            count.put(fruits[j], count.getOrDefault(fruits[j], 0) + 1);
            if (count.get(fruits[j]) == 1) {
                currentKind++;
            }
            
            while (i <= j && currentKind > 2) {
                count.put(fruits[i], count.get(fruits[i]) - 1);
                if (count.get(fruits[i]) == 0) {
                    currentKind--;
                }
                i++;
            }
            
            int amount = j - i + 1;
            max = Math.max(max, amount);
        }
        
        System.out.println(max);
    }
}