백준 30804번 과일 탕후루

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

 

백준의 알고리즘 분류는 브루트포스, 투포인터로 돼있지만

구현을 생각해봤을때 큐로 푸는 게 효율적일 거 같았다.

 

#include <iostream>
#include <queue>
using namespace std;

int fruits[10]={0};

bool check(){
    int c=0;
    for(int i=1; i<=9; i++)
        if(fruits[i]>0) c++;
    return c>2;
}

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

    int n, fruit, count=0, max=1;
    queue<int> skewer;
    cin >> n;

    for(int i=0; i<n; i++){
        cin >> fruit;
        fruits[fruit]++;
        skewer.push(fruit);
        count++;
        while(!skewer.empty() && check()){
            fruits[skewer.front()]--;
            skewer.pop();
            count--;
        }
        if(count>max) max=count;
    }
    cout << max;
    
    return 0;
}

 

앞에서 빼는 건 큐에서 pop 하면 되고 아직 안 넣은 것을 뒤에서 뺀 셈 치면 되기 때문에
다 꽂혀있는 상태가 아니라 하나씩 큐에 꽂아가는 방식으로 구현했다.

 

fruits 배열로 꽂혀있는 과일 수를 관리하여 2종류 초과로 꽂힐 시 2종류 이하가 될때까지 pop해준다.

그렇게 과일을 다 꽂으면서 최댓값을 갱신해준다.