[BOJ] 올바른 배열 1337번 C++

 

문제

올바른 배열이란 어떤 배열 속에 있는 원소 중 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보다 작을 때까지 이동하면서

필요한 원소의 최소 개수를 찾으면 된다!

 

만약 1,2,3,5,7,9가 있다면

i가 2일때

3,5,7은 3+5보다 작으므로

필요한 최소 개수는 2가 된다

 

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n; cin>>n;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin>>v[i];

    sort(v.begin(), v.end());

    int j=0, ans = 5;

    for(int i=0; i<n; i++) {
        while(j < n && v[j] < v[i]+5) {
            j++;
        }
        int len = j - i;
        ans = min(ans, 5-len);
    }

    cout<<ans;
}