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

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

문제

---

은하는 긴 막대에 𝑁개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 𝑆₁, 𝑆₂, ⋯, 𝑆_𝑁번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 𝑎개, 뒤에서 𝑏개의 과일을 빼면 𝑆_𝑎+1, 𝑆_𝑎+2, ⋯, 𝑆_{𝑁−𝑏−1}, 𝑆_𝑁−𝑏번 과일, 총 𝑁−(𝑎+𝑏)개가 꽂혀있는 탕후루가 됩니다. (0 ≤ 𝑎,𝑏; 𝑎 + 𝑏 < 𝑁)

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

입력

---

첫 줄에 과일의 개수 𝑁이 주어집니다. (1 ≤ 𝑁 ≤ 200000)

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 𝑁개의 정수 𝑆₁,⋯,𝑆_𝑁이 공백으로 구분되어 주어집니다. (1 ≤ 𝑆_𝑖 ≤ 9)

출력

---

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

 

문제 풀이

---

투 포인터 알고리즘을 이용한 문제.

탕후루의 첫 과일을 의미하는 start와, 마지막 과일을 의미하는 end 두 변수를 설정하여 start와 end 사이의 과일의 종류가 2개 이하가 되도록 탐색하며 가장 긴 길이를 찾아내면 된다. 과일의 종류는 1~9까지 있으므로 각 번호에 해당하는 과일이 탕후루에 몇 개 있는지 저장하는 배열을 하나 만든다. 

처음에는 start와 end를 둘 다 0으로 초기화하고, 탕후루의 첫 과일에 해당하는 번호의 개수를 1 증가시킨다. 그 이후 각 start에 대해 end를 증가시켜가며 종류가 2개가 넘거나 end가 N과 같아질 때까지 찾는다. 종류가 2개가 넘어가는 순간, end에 위치한 과일의 번호가 포함되지 말아야 하므로 end에 있던 과일의 종류에 해당하는 과일의 count를 1 감소시키고, end도 1 감소시킨다.

한 start에 대해 최대 범위를 구했다면 start를 증가시켜가며 계속 반복한다.

 

아래는 코드.

#include <iostream>
#include <set>
using namespace std;
int* fruitCounts;

int getCount()
{
	int fruitCount = 0;
	for (int i = 0; i < 10; i++)
	{
		if (fruitCounts[i] != 0)
		{
			fruitCount++;
		}
	}
	return fruitCount;
}

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

	int N;
	cin >> N;
	int* arr = new int[N];
	fruitCounts = new int[10];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (int i = 0; i < 10; i++)
	{
		fruitCounts[i] = 0;
	}
	int start = 0;
	int end = 0;
	int answer = 1;
	fruitCounts[arr[end]]++;
	while (start < N)
	{
		while (end<N)
		{
			end++;
			if (end >= N)
			{
				break;
			}
			fruitCounts[arr[end]]++;
			if (getCount() > 2)
			{
				fruitCounts[arr[end]]--;
				end--;
				answer = max(answer, end - start + 1);
				break;
			}
			else
			{
				answer = max(answer, end - start + 1);
			}
		}
		fruitCounts[arr[start]]--;
		start++;
	}
	cout << answer << "\n";
	return 0;
}