[BOJ] 30804번_과일 탕후루_두 포인터 (C++)

[문제]

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

주문이 들어와서 N개의 과일이 꽂혀있는 탕후루를 만들었다. 과일의 각 종류에는 1번부터 9번까지의 번호가 붙어있고, 앞쪽부터 차례대로 S1,S2,...,SN번 과일이 꽂혀있다. 탕후루를 다 만든 후 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었다.

탕후루를 다시 만들 시간이 없어 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기려고 할 때, 가장 많은 과일을 남길 수 있는 경우의 과일 개수를 구하는 문제이다.

[사용 알고리즘]

두 포인터

[풀이 핵심]

• 나는 두 포인터를 활용해서 문제를 해결했다. start와 end라는 두개의 포인터를 0으로 초기화 해주고 상황에 따라 포인터를 움직여가며 탕후루를 탐색했다. 풀이 순서는 다음과 같다.

  1. end 포인터를 한칸 옮겨준다. end++
  2. end번째에 꽂혀있는 과일의 종류를 늘려준다. kind[tang[end]]++
     2.1 이 때 총 과일의 종류가 2를 초과하면 end를 다시 이전으로 옮긴 후, 늘렸던 과일의 종류도 내린다. 그 이후에 break를 통해 3번의 result를 저장하는 단계로 넘어간다.
     *여기서 현재 탕후루가 몇 종류의 과일을 사용하고 있는지 확인해야하는데, 과일은 총 9종류이므로 간단하게 반복문을 사용해서 전부 검사하자.
  3. 1~2번을 반복하며 end가 N이 되었을 때 지금까지 탐색한 탕후루 중 가장 큰 탕후루랑 방금 탐색한 탕후루 중 큰 값을 result에 저장한다. result = max(result,end-start)
  4. 이후 start번째에 꽂혀있는 과일의 종류를 빼주고, start를 한칸 옮긴다.
  5. 위 과정을 start가 N이 될때까지 반복하면 result가 정답이다.

[코드]

//boj30804번_과일 탕후루_두 포인터

#include<iostream>

using namespace std;

int kind[10];
int tang[200001];

int Count() {
	int cnt = 0;

	for (int i = 0; i < 10; i++) {
		if (kind[i] != 0) {
			cnt++;
		}
	}

	return cnt;
}

int main() {
	int N;
	cin >> N;
		
	for (int i = 0; i < N; i++) {
		cin >> tang[i];
	}

	int start = 0;
	int end = 0;

	int result = 0;

	while (start < N) {
		while (end < N) {
			kind[tang[end]]++;
			end++;

			if (Count() > 2) {
				end--;
				kind[tang[end]]--;

				break;
			}
		}
		result = max(result, end - start);

		kind[tang[start]]--;
		start++;
	}

	cout << result;

	return 0;
}