https://www.acmicpc.net/problem/21967
문제
드높은 남산 위에 우뚝 선
(중략)
세워라 반석 위에
선린의 터를
반석: 넓고 펀펀한 큰 돌, 너럭바위
어떤 수열이 반석이라는 것은, 수열의 최댓값과 최솟값의 차이가 2 이하임을 의미한다.
예를 들어 1 2 3 3 1 2는 최댓값(3)과 최솟값(1)의 차이가 2이므로 반석이고, 2 6 5 4는 최댓값(6)과 최솟값(2)의 차이가 4이므로 반석이 아니다.
수열이 주어지면 수열의 연속한 부분 수열(부분 문자열, substring) 중, 가장 긴 반석의 길이를 구하는 프로그램을 작성하자.
입력
첫 번째 줄에 수열의 길이 N이 주어진다.
두 번째 줄에는 수열 A의 원소 A1,A2,⋯,AN이 공백으로 구분되어 주어진다.
출력
수열 A의 연속한 부분 수열 중 가장 긴 반석의 길이를 출력한다.
제한
1 ≤ N ≤ 1 000 000
1 ≤ Ai ≤ 10
문제 풀이
투 포인터 문제.
N이 1000000이므로 이중 for문으로는 해결할 수 없다. 특정 범위 안에 최댓값과 최솟값의 차이가 2 이하가 되도록 범위를 조정하는 투 포인터 알고리즘을 사용해주면 된다.
여러 방법이 있겠지만 Ai가 최소 1, 최대 10인 점을 활용해 큐를 이용해 각 숫자마다 인덱스를 저장한 후, 시작점을 옮길 때 각 숫자마다 다음 범위에 들어가는지 확인하여 최솟값과 최댓값을 업데이트해주는 방식으로 구현하였다.
Ai가 1~10까지이므로 최솟값-최댓값이 1-3, 2-4, 3-5, 4-6, 5-7, 6-8, 7-9, 8-10까지의 8가지의 경우밖에 존재하지 않는 점을 이용해 모든 경우를 탐색해도 된다.
아래는 코드.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
int N;
cin >> N;
int* arr = new int[N];
queue<int>* q = new queue<int>[11];
for (int i = 0; i < N; i++)
{
cin >> arr[i];
q[arr[i]].push(i);
}
int left = 0;
int right = 0;
int answer = 1;
int minValue = arr[0];
int maxValue = arr[0];
while (left < N)
{
while (true)
{
right++;
if (right >= N)
{
break;
}
minValue = min(minValue, arr[right]);
maxValue = max(maxValue, arr[right]);
if (maxValue - minValue > 2)
{
break;
}
else
{
answer = max(answer, right - left + 1);
}
}
right--;
q[arr[left]].pop();
minValue = 10;
maxValue = 1;
for (int i = 1; i < 11; i++)
{
if (!q[i].empty() && q[i].front() <= right)
{
minValue = min(minValue, i);
maxValue = max(maxValue, i);
}
}
left++;
}
cout << answer << "\n";
return 0;
}