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

안녕하세요 오늘 풀어볼 문제는 백준 과일 탕후루 입니다.

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

 

 

처음 문제를 봤을 때는 두 가지 풀이를 떠올렸어요.

1. dequeue를 사용해 일일이 경우의 수를 검사

2. n부터 시작하는 탕후루 중 가장 긴 경우들을 추출

 

두 경우 모두 O(n^2)의 시간 복잡도를 가지기 때문에 그다지 좋은 생각은 아니었네요.

 

이 문제는 투포인터 문제입니다.

투포인터란 수열의 시작과 끝 인덱스를 사용해 O(n)로 조건에 부합하며 연속된 수열을 검사하는 알고리즘이에요.

 

문제에서도 전형적인 투포인터 구현을 따랐습니다.

수열이 조건을 만족하는 중이거나 만족하지 못했다면 수열의 길이를 늘이고

if (cnt <= 2)
	r++;

 

조건을 만족하지 못했다면 수열의 길이를 줄였습니다.

else
	l++;

 

 

문제에서 요구하는 조건은 '사용된 과일의 가짓수를 2개 이하로' 입니다.

가짓수 별로 사용된 개수를 파악하기 위해 배열을 사용해줬어요.

4번 과일을 추가로 고려했으면 아래처럼 됩니다.

type[4]++;

 

투 포인터와 문제의 조건을 결합한 코드는 아래처럼 되겠네요.

if (cnt <= 2) {
	r++;
	if (r >= N) break;

	if (type[tanghulu[r]] == 0)
		cnt++;
	type[tanghulu[r]]++;
}
else {
	type[tanghulu[l]]--;
	if (type[tanghulu[l]] == 0)
		cnt--;

	l++;
}

 

 

저는 프로세스를 잘 짜놓고 한 가지 놓친 부분이 있었습니다.

바로 수열의 초기화인데요.

 

처음에 두 포인터 l과 r은 동일하게 0의 값을 가집니다.

수열에 0번 과일은 이미 포함되어있다는 뜻이죠.

초기 변수들을 아래와 같이 설정해줘야 합니다.

int mx = 1;
int cnt = 1;
type[0]++;

 

 

아래는 코드 전문

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

int N;
vector<int> tanghulu;
int mx = 1;
int type[10] = { 0, };
int cnt = 1;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int fruit;
		cin >> fruit;
		tanghulu.push_back(fruit);
	}

	int l = 0, r = 0;

	type[0]++;

	while (1) {
		if (r >= N) break;

		if (cnt <= 2) {
			r++;
			if (r >= N) break;

			if (type[tanghulu[r]] == 0)
				cnt++;
			type[tanghulu[r]]++;
		}
		else {
			type[tanghulu[l]]--;
			if (type[tanghulu[l]] == 0)
				cnt--;

			l++;
		}

		if (cnt <= 2) mx = max(r - l + 1, mx);
	}
	
	cout << mx;
}

 

도움이 되셨다면 마음과 댓글 부탁드립니다.