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

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

풀이

투 포인터 알고리즘을 활용하여, 시작점을 고정시켜놓고 끝점을 늘려나다가, 과일의 개수가 2개를 초과하면 시작점을 하나씩 앞으로 당겨오는 방식을 반복

과일의 개수가 2개를 초과하거나 주어진 배열 밖으로 벗어날 경우 구간의 길이를 구하여 max값을 업데이트해 준다

 

제출 코드

#include <iostream>
using namespace std;

int fruit[200001];
int fCount[10];
bool check()
{
    int cnt = 0;
    for (auto& f : fCount)
        if (f > 0) cnt++;
    return cnt <= 2;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, start = 0, end = 0, maxCount = 0;
    cin >> n;
    for (int i = 0; i < n; i++) // 입력받기
        cin >> fruit[i];
    while(start < n)
    {
        while(end < n)
        {
            fCount[fruit[end]]++;
            if (!check()) break;
            end++;
        }
        maxCount = max(maxCount, end - start);
        end++;
        fCount[fruit[start]]--;
        start++;
    }
    cout << maxCount;
}