[Baekjoon] 30804번: 과일 탕후루

🥅 문제

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

 

🔍 설계

꼬치에 과일을 모두 꽂아놓고 양끝에서 빼는 것은 앞에서부터 하나씩 끼우고 꽂힌 과일의 종류가 2개를 넘으면 앞에 있는 과일을 빼는 것과 같다. 아직 꽂히지 않은 과일들은 뺐다고 생각하면 되기 때문이다.

 

과일을 하나씩 끼우고, 꼬치에 현재 없는 과일이라면 과일의 종류를 하나 증가시킨다. 꼬치에 꽂혀있는 과일의 종류가 2개를 초과한다면, 2개가 될 때까지 앞에서부터 뺀다. 2개가 되었으면 결과값을 갱신한다.

 

👊 풀이

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

int n, fruit, type = 0, result = 0;
vector<int> fruit_count(10);
queue<int> stick;

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> fruit;
		stick.push(fruit);

		if (fruit_count[fruit] == 0) {
			type += 1;
		}
		fruit_count[fruit] += 1;

		while (type > 2) {
			int front_fruit = stick.front();
			stick.pop();
			fruit_count[front_fruit] -= 1;
			if (fruit_count[front_fruit] == 0) {
				type -= 1;
			}
		}
		
		result = max(result,(int)stick.size());
	}
	cout << result << "\n";

	return 0;
}