[BOJ S4][C++] 백준 1337번: 올바른 배열

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

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개가 되면 stop

 

그렇게 종류별로 나온 답들 중 최솟값을 골라 출력

이때, 만약 최솟값이 4보다 크다면 그냥 4가 출력되도록 설정하였다.

 

// Authored by : seondal
// 풀이 : https://whkakrkr.tistory.com/
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v;
    vector<int> sub;
    int n;
    cin >> n;
    while(n--) {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    sort(v.begin(), v.end());
    
    int ans = 4;
    for(int i=0; i<v.size()-1; i++) {
        int tmp = 0, cnt = 1;
        for(int j=i; j<v.size()-1; j++){
            if(cnt == 5) {
                ans = min(ans, tmp);
                break;
            }
            int cha = v[j+1] - v[j] - 1;
            tmp += cha;
            cnt += cha + 1;
        }
        if(cnt < 5) {
            tmp += 5 - cnt;
            ans = min(ans, tmp);
        }
    }
    
    cout << ans;
    
    return 0;
}
    
/**/

 

풀이2

조원들과 토론하다가 알게된 사실..

굳이 그 차를 구해서 계산해주고 있을 필요가 없었다 ㅠㅠ

 

그냥 그 연속된 수의 범위 안에 들어오는지 체크만 하고

그 갯수를 세어서 답을 구해주는게 훨씬 빠르고 간단했다

 

// Authored by : seondal
// 풀이 : https://whkakrkr.tistory.com/
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v;
    vector<int> sub;
    int n;
    cin >> n;
    while(n--) {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    sort(v.begin(), v.end());
    
    int ans = 0;
    for(int i=0; i<v.size(); i++){
        int cnt = 0;
        for(int j=1; j<5 && i+j<v.size(); j++)
            if(v[i]+5 > v[i+j]) cnt++;
        ans = max(ans, cnt);
    }
    
    cout << 4 - ans;
    
    return 0;
}
    
/**/