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

과일 탕후루

 길이가 N인 막대에 N개의 과일을 순서대로 꽂은 탕후루가 있을 때 과일이 2종류만 남을 때까지 맨 앞 또는 맨뒤에서 제거하여 만들 수 있는 탕후루 길이의 최댓값을 구하는 문제입니다.

알고리즘

// 과일을 최대 두종류만 기억한다.
// 새로운 과일이 들어오면 기존 과일꼬치의 길이를 계산하고 가장 앞쪽의 과일뭉치를 제거한다.
// 입력이 끝날때 까지 반복한다.

int fruit1, start1, end1, fruit2, start2, end2;
while(//과일 순서를 입력받는 동안)
{
    if(과일1 또는 과일2가 입력되었을 때)
    	end1 또는 end2의 값을 현재 좌표로 수정
    else
    	// 새로운 과일이 들어왔을 때
        // 지금까지의 과일 길이를 계산
        // 새로운 과일과 남은 과일의 좌표 수정
}
// 과일의 길이 계산
cout<<max_len;

코드

#include <iostream>

using namespace std;

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

	int n;
	cin >> n;

	int max_len = 0;
	int fruit1 = -1, start1 = -1, end1 = -1;
	int fruit2 = -1, start2 = -1, end2 = -1;
	for (int i = 0; i < n; ++i)
	{
		int fruit;
		cin >> fruit;
		if (fruit == fruit1)
		{
			end1 = i;
		}
		else if (fruit == fruit2)
		{
			end2 = i;
		}
		else
		{
			if (fruit1 == -1)
			{
				fruit1 = fruit;
				start1 = i;
				end1 = i;
				continue;
			}
			else if (fruit2 == -1)
			{
				fruit2 = fruit;
				start2 = i;
				end2 = i;
				continue;
			}
			int st = start2 == -1 ? start1 : (start1 < start2 ? start1 : start2);
			int ed = end2 == -1 ? end1 : (end1 > end2 ? end1 : end2);
			int le = ed - st + 1;
			max_len = le > max_len ? le : max_len;
			if (end1 < end2)
			{
				start2 = end1 + 1;
				fruit1 = fruit;
				start1 = i;
				end1 = i;
			}
			else
			{
				start1 = end2 + 1;
				fruit2 = fruit;
				start2 = i;
				end2 = i;
			}
		}
	}
	int st = start2 == -1 ? start1 : (start1 < start2 ? start1 : start2);
	int ed = end2 == -1 ? end1 : (end1 > end2 ? end1 : end2);
	int le = ed - st + 1;
	max_len = le > max_len ? le : max_len;

	cout << max_len;

	return 0;
}

 

느낀점

 처음에는 컨테이너를 이용해 보려고 하였습니다만 입력의 크기가 200,000 이기 때문에 연산 과정에서 시간초과가 날 것 같았습니다. 좀 생각해 보니까 과일의 시작좌표와 끝 좌표만 기억해도 해결할 수 있을 것 같아서 위와 같은 방법으로 풀어봤습니다.