백준 1337번: 올바른 배열 (C++)

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

1337번: 올바른 배열

---

Level: Silver IV

Solved By: Implementation

 

처음에 정렬을 하여 인접한 원소들 간의 차를 활용한다면 규칙이 있을까 했는데 찾을수록 오류가 발견되어 직접 구현해보는 게 아이디어였습니다.

구현이 가능하였던 이유는 원소의 최대 개수가 50개이고, 한 원소당 5가지의 케이스를 고려하여서 시간초과를 면할 수 있기 때문입니다.

 

한 원소를 기준으로 해당 원소가 첫 번째에 있을 때를 생각하여 +1인 원소는 있는지 +2인 원소는 있는지...

혹은 두 번째에 있을 때를 생각하여 -1인 원소는 있는지 +1인 원소는 있는지...

이와 같이 5가지 모두를 고려한다면 답을 구할 수 있었습니다.

원소의 유무는 map을 이용하였습니다. m.find()를 사용하였을 때, 원소가 없다면 m.end() iterator를 반환하기 때문에 이 특성을 활용하여 조건을 만들어주었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define MAX 1e9
using namespace std;

int N;
vector<int> v;
map<int, bool> m;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    for(int i = 0; i < N; i++){
        int a; cin >> a; 
        m.insert({a, true});
        v.push_back(a);
    }
    
    int res_cnt = 0;
    for(auto t : v){
        for(int k = -4; k <= 0; k++){
            if(t + k < 0) continue; // 탐색하는 수 바운더리가 0 미만
            if(t - k > MAX) continue;
            
            int cnt = 0;
            
            for(int i = t + k; i <= t + k + 4; i++){
                if(m.find(i) != m.end()) cnt++;
            }
            
            res_cnt = max(res_cnt, cnt);
        }
    }
    
    cout << 5 - res_cnt;
    
    return 0;
}