[JAVA] 백준 (실버2) 30804번 과일 탕후루

링크

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

---

문제 설명

정답률 34.600%

은하는 긴 막대에
$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)$ 

---

출력

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

---

풀이

N의 최댓값은 20만으로 모든 인덱스에 대해 반복하면서 각 구간마다 일일이 과일의 종류를 확인하면 시간복잡도는 $O(n^2)$으로 비효율적이므로 시간초과가 발생한다. 따라서 투 포인터를 이용해 $O(n)$의 시간복잡도로 해결한다.

우선 투 포인터를 위한 변수는 다음과 같이 선언한다. start와 end를 하나씩 증가시키며 탕후루 배열의 끝까지 탐색하면서 조건에 만족하는 탕후루의 최대 길이를 구한다.

int start = 0;
int end = 0;
int typeCount = 0;  //현재 구간의 과일 종류
int maxLength = 0;  //탕후루의 최대 길이

우선 끝 인덱스를 N - 1까지 하나씩 증가시키며 현재 구간의 과일의 종류를 카운트한다. 이때 과일의 종류가 2개가 넘는다면 시작 인덱스도 증가시키는데 증가시키면서 구간에서 제외된 과일으로 인해 해당 과일의 개수가 0이 된다면 현재 구간의 과일 종류도 1이 줄어든다.

//end가 N - 1이 될 때까지 반복
for (int end = 0; end < N; end++) {
    //새로운 과일이 나타날 경우 종류 카운트
    if (fruitCount[tanghulu[end]] == 0) {
        typeCount++;
    }
    fruitCount[tanghulu[end]]++;
    
    //과일의 종류가 2개가 넘을 경우
    while (typeCount > 2) {
        fruitCount[tanghulu[start]]--;
        //구간에서 제외된 과일의 개수가 0이면 종류도 줄어든다.
        if (fruitCount[tanghulu[start]] == 0) {
            typeCount--;
        }
        start++;
    }
    maxLength = Math.max(maxLength, end - start + 1);
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] tanghulu = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int[] fruitCount = new int[10];  //1 ~ 9번의 과일 개수

        int start = 0;
        int typeCount = 0;  //현재 구간의 과일 종류
        int maxLength = 0;  //탕후루의 최대 길이

        for (int end = 0; end < N; end++) {
            //새로운 과일이 나타날 경우 종류 카운트
            if (fruitCount[tanghulu[end]] == 0) {
                typeCount++;
            }
            fruitCount[tanghulu[end]]++;

            //과일의 종류가 2개가 넘을 경우
            while (typeCount > 2) {
                fruitCount[tanghulu[start]]--;
                //구간에서 제외된 과일의 개수가 0이면 종류도 줄어든다.
                if (fruitCount[tanghulu[start]] == 0) {
                    typeCount--;
                }
                start++;
            }

            maxLength = Math.max(maxLength, end - start + 1);
        }

        System.out.println(maxLength);
    }
}