[Silver 2] 30804 과일 탕후루

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

 

탕후루를 끼울 때 순차적을 끼울 수 있다고 생각하고, 다른 종류의 과일이 2보다 클 경우 앞에서 부터 과일을 제거하면 해결할 수 있다.

따라서 1 <= Fruit <= 9까지의 값을 가지는 과일의 종류를 셀 수 있는 cnt배열을 생성한다.

 

과일 값을 입력 받은 후 cnt배열에 값이 0인지 검사(처음 끼우는 과일인지 검사) 한 후 cnt배열의 값을 1증가시킨다.

이 후 처음 끼우는 과일인 경우 other 변수를 1 증가(과일 종류를 세는 변수)시킨다.

 

other 변수의 값이 2보다 큰 경우 queue에서 과일 하나를 빼고 cnt 배열에서 값을 1 감소시킨다. (과일을 제거했기 때문)

만약 제거한 과일이 탕후루 꼬치에 존재하지 않는 과일(cnt배열의 값이 0)인 경우 other 변수를 1 감소시킨다.

 

큐의 과일 개수를 구하고 정답 변수와의 값 비교를 통해 최소 값을 저장한다

 

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

int N;
int cnt[10], other = 0, answer = 0;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    queue<int> q;
    int fruit;
    for(int i = 0;i<N;i++){
        cin>>fruit;
        q.push(fruit);

        if(cnt[fruit]++ == 0){
            other++;
        }
        while(other > 2){
            fruit = q.front();
            q.pop();
            cnt[fruit]--;
            if(cnt[fruit] == 0){
                other--;
            }
        }
        answer = max(answer, static_cast<int>(q.size()));
    }
    cout<<answer;
}