[백준 1337] 올바른 배열 (C++)

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

문제

---

올바른 배열이란 어떤 배열 속에 있는 원소 중 5개가 연속적인 것을 말한다. (연속적인 것이란 5개의 수를 정렬했을 때, 인접한 수의 차이가 1인 것을 말한다.)

예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.

배열이 주어지면, 이 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 개수를 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 배열에 중복되는 수는 없다.

 

출력

---

첫째 줄에 입력으로 주어진 배열이 올바른 배열이 되게 하기 위해서 추가되어야할 원소의 최소 개수를 출력한다.

 

문제 풀이

---

투 포인터 문제.

 

배열의 원소 중 아무거나 5개 연속이면 된다. 특정 원소를 연속하는 5개 원소 중 첫 숫자라 가정하면 그 숫자에 +4 한 숫자까지 모두 들어 있어야 한다. +1부터 +4까지의 범위에 해당하는 숫자가 몇 개 있는지 확인한다. 예를 들어 첫 숫자가 1이고, 4와 5가 있다면 남은 것은 2와 3 2개가 된다. 첫 숫자가 1이고, 2와 4가 있다면 남은 것은 3과 5 2개가 된다. 예시에서 확인할 수 있듯이 +1부터 +4까지의 범위는 연속과 상관없이 개수만 세어주면 된다.

투 포인터를 이용해 5 이상이면 다음 원소를 탐색하게 하여 첫 원소를 포함한 최대 길이를 구한 후 5에서 해당 숫자를 빼주면 된다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	int start = 0;
	int end = 0;
	int maxLength = 0;
	while (start < N)
	{
		while (true)
		{
			end++;
			if (end >= N || arr[end] - arr[start] > 4)
			{
				break;
			}
		}
		end--;
		maxLength = max(maxLength, end - start + 1);
		start++;
	}
	cout << 5 - maxLength << "\n";
	return 0;
}