[Baekjoon] 30804: 과일 탕후루 - (C3, S2) Brute Force, Tow Pointers

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

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

30804번: 과일 탕후루

 

투 포인터 방식을 사용해 브루트포스 알고리즘으로 풀 수 있는 문제이다. 투 포인터 방식은 배열이나 리스트에서 두 개의 포인터를 사용하여 효율적으로 특정 조건을 만족하는 구간이나 값을 찾는 알고리즘 기법이다.

 

구간의 시작점을 나타내는 left 포인터와, 구간의 끝점을 나타내는 right 포인터를 사용한다. right 포인터를 이동시키면서 탐색 범위를 확장하고, 구간 내의 조건을 만족시키지 않으면 left 포인터를 이동시켜 범위를 축소한다.

 

이 문제에서는 막대의 양 끝에서 과일을 제거할 수 있다. 즉, 두 종류 이하의 과일만 포함된 가장 긴 구간의 길이를 찾아야 한다.이를 위해 [left, right] 범위 내에서 두 종류 이하의 과일만 포함하도록 범위를 조정한다. 그리고 구간의 길이 right - left + 1을 최대값으로 갱신한다. 이를 right을 막대의 끝까지 증가시키면서 반복하면 조건을 만족하는 최대 구간의 길이를 얻을 수 있다. 

 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<int> t(N); // 탕후루에 꽂힌 과일 번호

    // 현재 윈도우 내 과일 종류별 빈도수 관리
    unordered_map<int, int> freq;

    for (int &val : t)
        cin >> val;

    int left = 0;       // 윈도우의 시작 위치
    int max_length = 0; // 조건을 만족하는 최대 구간 길이

    // 오른쪽 포인터를 이동하며 윈도우를 확장
    for (int right = 0; right < N; right++)
    {
        freq[t[right]]++; // 윈도우에 현재 과일 추가

        // 윈도우 내 과일 종류가 2개를 초과하면 축소 시작
        while (freq.size() > 2)
        {
            freq[t[left]]--; // 왼쪽 끝의 과일 제거
            if (freq[t[left]] == 0)
                freq.erase(t[left]); // 빈도가 0이 되면 삭제

            left++; // 윈도우 시작점 이동
        }

        // 현재 윈도우 길이를 계산하고 최대값 갱신
        max_length = max(max_length, right - left + 1);
    }

    cout << max_length;
    return 0;
}