백준 21967 세워라 반석 위에

 

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

21967번: 세워라 반석 위에

풀이

먼저 deque하나를 선언하겠습니다.

 

해당 deque는 i번째 숫자까지 포함했을때 반석을 만족하는 가장 큰 연속한 부분 수열로 정의하겠습니다.

 

i번째숫자를 deque에 넣은 뒤에 반석인지 아닌지 검사를 하고

반석이 아니라면 deque의 맨앞요소를 제거 

반석이라면 정답결과를 갱신해주면 됩니다.

 

 

하지만 deque의 모든 요소를 검사해서 반석임을 확인하는 것은 O(N)의 시간복잡도가 걸립니다.

결국 문제를 해결하는데 O(N^2)의 시간 복잡도가 걸리게 되고 시간초과를 받게됩니다. ㅠㅠ

 

문제의 제한을 확인하면 입력으로 들어가는 A값이 1이상 10이하임을 알 수 있습니다.

deque내부에 1~10까지 숫자가 몇개 들어있는지만 검사하면됩니다.

 

배열을 정의하겠습니다. 

Num[i] : 현재 deque가 숫자 i를 포함하는 갯수

ex) Num[3] = 4이면 // deque에 3이 4개가 있다는 이야기

 

 

해당 배열을 이용해서 현재 deque가 반석인지 확인하면 됩니다. (코드참고)

 

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

int N;
int Num[11];
int Check()
{
	int a = 0;
	for (int i = 1; i <= 10; i++)
		if (Num[i] > 0)
		{
			a = i;
			break;
		}
	int b = 0;
	for (int i = 10; i >= 1; i--)
		if (Num[i] > 0)
		{
			b = i;
			break;
		}
	return b - a;
}
deque<int> Q;

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

	int N;
	cin >> N;
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		Num[a]++;
		Q.push_back(a);
		while (Check() > 2 && !Q.empty())
		{
			int b = Q.front();
			Q.pop_front();
			Num[b]--;
		}
		ans = max(ans, (int)Q.size());
	}

	cout << ans << endl;
}

 

-----------------------------------------------------------------------------------------------------------------------------------

질문은 언제나 환영합니다.