[Java] BOJ 30804 과일 탕후루

문제 

문제 링크 https://www.acmicpc.net/problem/30804

• 은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다.
• 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,SN번 과일이 꽂혀있습니다.
• 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.
• 이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.
• 탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다.
• 앞에서 a개, 뒤에서 b개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b번 과일, 총 N−(a+b)개가 꽂혀있는 탕후루가 됩니다. (0 ≤ a, b; a+b < N)
• 첫 줄에 과일의 개수 N이 주어집니다. (1 ≤ N ≤ 200000)
• 둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 S1,⋯,SN이 공백으로 구분되어 주어집니다. (1 ≤ Si ≤ 9)
• 문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

아이디어

• 끝점을 기준으로 끝점을 점점 늘려가면서 과일의 종류와 개수를  HashMap에 저장해준다.
• 끝점을 늘려, 과일의 종류를 추가했는데 과일의 종류가 2 초과가 된다면 시작점 과일 종류의 개수를 1개 빼준다. (시작점은 0으로 시작)
• 만약 시작점의 과일 개수가 0개라면, 과일 종류에서 시작점 과일 종류를 제거해준뒤, 시작점을 증가시킨다.
• 그리고 현재의 끝점과 시작점 간격과 max값 중 더 큰 값으로 max값을 갱신한다. (끝점과 시작점의 간격이 과일의 개수이므로)

겪은 시행착오

• 처음에 삼중 for문을 써서 투포인터 방식으로 풀었다가 시간초과가 났다... (투포인터로 푼게 아니였나...?)
• 그래서 시간초과를 해결하기가 조금 힘들었다... ㅜㅜ

투 포인터... 기억하자...!

코드

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

public class BOJ30804 {
    public static void main(String[] args) throws Exception{
        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++){
            int n = Integer.parseInt(st.nextToken());

            arr[i] = n;
        }

        // 과일의 개수 최댓값을 저장할 변수
        int max = Integer.MIN_VALUE;
        // 시작점
        int s = 0;
        // 과일의 종류를 저장할 HashMap (과일의 종류와 개수를 저장)
        HashMap<Integer, Integer> fruits = new HashMap<>();

        // 끝정
        for(int i = 0; i < N; i++){
            // 현재 과일을 과일 종류에 추가하고
            // 만약 해당 과일이 없다면 0에 1을 추가하고
            // 기존에 있다면 기존 값에 1을 더해서 저장함
            fruits.put(arr[i], fruits.getOrDefault(arr[i], 0) + 1);

            // 과일의 종류가 2개 초과가 된다면
            while(fruits.size() > 2){
                // 앞에서부터 없애야하므로
                // 시작점의 과일 개수를 1개 줄임
                fruits.put(arr[s], fruits.get(arr[s]) - 1);

                // 만약 시작점 과일의 종류 개수가 0이 된다면
                // 해당 과일의 종류를 HashMap에서 제거
                if(fruits.get(arr[s]) == 0){
                    fruits.remove(arr[s]);
                }

                // 시작점을 증가시킴
                s = s + 1;
            }

            // 현재 최대값과 (끝점 - 시작점 + 1)한 크기와 비교해서
            // 더 큰 값을 최대값으로 갱신
            max = Math.max(max, i - s + 1);
        }

        System.out.println(max);
    }
}