30804 - 과일 탕후루

문제

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

느낀점

생각하는 것 자체는 어렵지 않았던 것 같은데, 완전 탐색으로 풀었다가 시간초과가나서 투포인터로 풀었다. 투포인터에서 왼쪽, 오른쪽 값을 어떻게 움직여야하는가를 생각하는게 어려웠다. 투포인터 문제에 더 익숙해지자

풀이

#include <iostream>
#include <deque>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    cin >> N;
    deque<int> fruits;
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        fruits.push_back(temp);
    }
    int left = 0;
    int maxValue = 0;
    int distinct = 0;

    vector<int> fruitsCount(10, 0);
    for (int start = 0; start < N; start++)
    {
        if (++fruitsCount[fruits[start]] == 1)
        {
            distinct++;
        }
        while (distinct > 2)
        {
            if (--fruitsCount[fruits[left]] == 0)
            {
                distinct--;
            }
            left++;
        }

        maxValue = max(maxValue, start - left + 1);
    }

    cout << maxValue;

    return 0;
}