[C++][백준 30804] 과일 탕후루

문제

접근 방법

한 방향으로 간다고 생각하면 된다.
하나씩 과일을 꽂으며 만약 종류가 2개를 넘어간다면 꽂혀있던 과일을 빼주는 것이다.

코드

#include <iostream>
#include <queue>
using namespace std;
int N, types, cnt[10], answer;
queue<int> q;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    while (N--)
    {
        int fruit;
        cin >> fruit;

        q.push(fruit);

        if (cnt[fruit]++ == 0)
        {
            ++types;
        }

        while (types > 2)
        {
            fruit = q.front();
            q.pop();

            if (--cnt[fruit] == 0)
            {
                --types;
            }
        }

        answer = max(answer, static_cast<int>(q.size()));
    }

    cout << answer;
    return 0;
}

풀이

각각의 종류마다 개수를 세어주면서 몇 종류가 존재하는지 확인해 주어야 한다.
과일을 하나씩 꽂으면서 만약 2 종류를 넘어가면 2종류가 될 때까지 이미 꽂혀있던 과일을 빼주고 2 종류 이하가 되었다면 개수를 세어주면 된다.