[백준] 과일 탕후루

🔗 문제 보기 - [백준] 과일 탕후루

📖 문제

은하는 긴 막대에 $N$개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 $1$부터 $9$까지의 번호가 붙어있고, 앞쪽부터 차례로 $S_1, S_2, \cdots, S_N$번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 $a$개, 뒤에서 $b$개의 과일을 빼면 $S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_{N-b}$번 과일, 총 $N-(a+b)$개가 꽂혀있는 탕후루가 됩니다. $(0 \le a, b;$ $a+b < N)$ 

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

✍ 입력

첫 줄에 과일의 개수 $N$이 주어집니다. $(1 \le N \le 200\,000)$ 

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 $N$개의 정수 $S_1, \cdots, S_N$이 공백으로 구분되어 주어집니다. $(1 \le S_i \le 9)$

📄 출력

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
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());  
        StringTokenizer st = new StringTokenizer(br.readLine());  
  
        int[] arr = new int[n];  
        for(int i = 0; i < n; i++) {  
            arr[i] = Integer.parseInt(st.nextToken());  
        }  
  
        Map<Integer, Integer> map = new HashMap<>();  
        int left = 0;  
        int maxLength = 0;  
        for(int right = 0; right < n; right++) {  
            map.put(arr[right], map.getOrDefault(arr[right], 0) + 1);  
  
            while(map.size() > 2) {  
                map.put(arr[left], map.get(arr[left]) - 1);  
                if(map.get(arr[left]) == 0) {  
                    map.remove(arr[left]);  
                }  
  
                left++;  
            }  
  
            maxLength = Math.max(maxLength, right - left + 1);  
        }  
        
        System.out.println(maxLength);  
    }  
}

🧩 코드풀이

해당 문제는 투포인터 라는 개념으로 접근하는 문제입니다.
LEFT (구간의 시작점) 과 RIGHT (구간의 끝점) 두가지를 이용해서 가장 긴 길이를 가진 구간의 길이를 출력해주면 됩니다.

1. right를 0부터 n 까지 증가 시키면서 Map에 과일의 종류와 과일의 갯수 + 1 해주는 식으로 추가해줍니다.
2. 과일의 종류를 추가시킨 Map의 크기가 2를 넘었을 때, 반복문을 이용하여 가장 좌측의 과일 종류의 과일 갯수 - 1 해주면서 left 인덱스 값도 1씩 증가시켜줍니다.
3. 이후 maxLength를 갱신해줍니다. 갱신할 때 rigth - left와 +1을 해주는데 +1을 하는 이유는 인덱스는 0부터 시작하지만 길이는 1부터 세기 때문입니다.