[백준] 2413번 비슷한 순열 (C++) 문제 풀이

[백준] 2413번 비슷한 순열 (C++) 문제 풀이

2413번: 비슷한 순열

개인적으로 재미있는 문제라고 생각해서 블로그에 포스팅 해야겠다고 생각했다.

 

2413번 비슷한 순열

분류 : 그리디 알고리즘

난이도 : 골드 2

정답률 : 41%

 

조건

• 각 숫자와 최대 1 차이가 나야한다.
• 가장 작은 순열을 찾아야 한다.

해당 조건을 자세하게 생각해보면 다음과 같은 특이점을 찾을 수 있다.

(1) 모든 숫자가 1번씩 나타나야 하고, A에는 (A-1, A, A+1)만 사용 가능하므로, 만약 A라는 수 자리에 A-1 수를 사용하게 되면 A-1에는 무조건 A를 사용해야 한다. 예를 들어서 7자리에 6을 사용하게 된다면, 6 자리에는 원래 5,6,7이 가능하지만, 6은 이미 사용되었으므로 쓸 수 없고, 5를 사용하게 된다면, 7은 8자리에 써야 하는데.. (8은 9자리에 써야하고.. 9는 10자리에...) 등등 이렇게 하면 부족할 수 밖에 없다. 따라서 무조건 6자리에는 7만 가능하게 된다.

(2) 가장 작은 순열을 찾아야 하므로 A자리에 A-1을 사용할 수 있는 지 체크해본다. 사용가능하다면 1번과 같이 사용하고, 불가능하다면 그냥 A를 사용하면 된다.

 

#include <iostream>

using namespace std;

bool used[50001];
int check[50001];
int A[50000];
int N;

int main(){
    cin >> N;

    for(int i=0; i<N; i++){
        cin >> A[i];
    }

    for(int i=1; i<=N; i++){
        check[i] = i;
    }

    for(int i=0; i<N; i++){
        int now = A[i];
        if(check[now] == now+1){
        	used[now] = true;
            cout << now+1 << " ";
        }
        else if(now!=1 && check[now] == now && check[now-1] == now-1 && !used[now] && !used[now-1]){
            used[now-1] = true;
            cout << now-1 << " ";
            swap(check[now], check[now-1]);
        }
        else{
            used[now] = true;
            cout << now << " ";
        }
    }

    return 0;
}