[C++] BaekJoon 30804 과일 탕후루

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

---

주어진 문제는 막대에 꽂힌 과일들 중에서 두 종류 이하의 과일만 남도록 앞쪽과 뒤쪽에서 몇 개의 과일을 빼내어 과일의개수가 가장 많은 경우를 찾는 것이다. 

 

조건:

1. 과일의 총 개수 N이 주어짐 

2. 과일의 종류는 1부터 9까지이며, 각 과일은 S1,S2,....,SN과 같이 나열된다.   

3. 앞에서 a개 뒤에서 b개의 과일을 뺼 수 있다. 

4. 두 종류 이하의 과일만 남기도록 하여, 남은 과일의 개수가 최대가 되도록 해야 한다.   

 

이 문제를 어떻게 접근해야 할까?

접근 방법을 두 케이스로 나눠봤다.

 

접근 방법:

1. 빈도수 카운트:

- 각 과일의 빈도 수를 카운트하여, 현재 과일 종류를 추적

- 빈도 수를 관리하여, 두 종류를 초과하면 앞쪽에서부터 과일을 제거하여 축소      

 

2. 최대 길이 갱신:

- 조건을 만족하는 가장 많이 나타난 과일의 빈도수를 추적하고 갱신   

 

코드

#include <iostream>
#include <queue>

using namespace std;

queue<int> stick; //탕후루 꼬치에 꽃힌 과일을 저장하는 큐
int type, cnt[10], answer; //type : 과일 종류, cnt[10] : 과일 빈도수 카운트(최대 10종류 과일)

void processfruit(int fruit); //함수 전방 선언

int main()
{
	int N; //과일의 개수

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int S; //과일의 종류 (1~9)
		cin >> S;
		processfruit(S);
	}

	cout << answer;
	return 0;
}

void processfruit(int fruit)
{
	stick.push(fruit);

	if (cnt[fruit]++ == 0) //cnt 배열의 값, 즉 빈도수를 증가시키고 만약 이 과일이 처음 나타났다면
	{
		++type; //과일 종류를 증가시킨다
	}
	while (type > 2) //과일의 종류가 2개가 남을떄까지 반복
	{
		int target;
		target = stick.front(); //큐의 맨 앞을 변수에 저장
		stick.pop();
		if (--cnt[target] == 0) //target이 더 이상 남지 않을 때, 
		{
			--type; //type 삭제 (1 -> 0)
		}
	}

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