[ BOJ 1071 ] 소트

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

문제

$N$개의 숫자가 주어진다. 이 때, $A[i]+1\neq A[i+1]$이 되지 않게 숫자의 순서를 바꾸고자 한다.

만약 답이 여러개면 사전순으로 제일 빠른 것을 출력하라.

풀이

풀이의 시작은 제일 빠른에 있다.

제일 빠른 것을 출력할려면 일단 숫자를 최대한 작게 하되 "필요할 때만" 바꿔줘야 한다.

예를 들어서 1 3 4 4 이렇게 있으면 굳이 안바꿔도 위 조건을 만족시키기 때문에 상관이 없다는 것이다.

하지만 3 4 4 1 이렇게 인풋이 들어오면 1이 제일 앞에 오게 바꿔줘야 한다.

따라서 먼저 들어온 input들을 정렬해서 그 이후 순서를 적절히 바꿔줘야 함을 알 수 있다.

이제 정렬되었다고 가정하자.

$A_i,\ A_{i+1},\ \cdots$에서 $A_{i+1}=A_i+1$라고 하자.

문제의 조건을 만족하지 않으므로 바꿔줘야 할 필요가 있다.

이 때, 바꿔줄 때 두 가지 경우의 수가 나온다.

1) $A_{i+1}$보다 큰 숫자가 배열에 없을 때

즉, $A_{i+1}$가 배열의 최댓값일 때를 의미한다.

이 때는 딱히 바꿔줄 수가 없으므로, "그룹 전체"를 바꿔줘야 한다.

무슨 의미냐면 예제 2번에

1 1 1 1 2 2 2 이렇게 있으면 2보다 큰 숫자가 없으므로

숫자가 1인 그룹이랑 2인 그룹이랑 완전히 바꿔줘야 한다는 뜻이다.

그러면 2 2 2 1 1 1 1 이 되므로 문제가 없어진다.

2) $A_{i+1}$보다 큰 숫자가 배열에 있을 때 (이하 $A_j$)

그러면 $A_j$랑 $A_{i+1}$이랑 바꿔주는 식으로 진행하면 된다.

이후 다 돌면서 계산하면 된다.

난 map을 이용하여 구현하였는데, 그러면 2)번 경우를 처리하기가 생각보다 곤란해진다.

바꿔준다는 것을 구현하기가 힘들기 때문이다.

이를 해결하기 위해선 바꿔준다로 접근하는 것이 아니라 $A_j$의 숫자를 사이에 insert하고 숫자의 개수를 하나 빼면 된다.

자세한건 구현 참고

구현

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    map<int, int> mp;
    scanf("%d",&n);
    for(int i=0, x;i<n;i++) scanf("%d", &x), mp[x]++;
    vector<pair<int, int> > seq(mp.begin(), mp.end()); // map을 그대로 담는 친구
    for(int i=0;i<seq.size()-1;i++)
    {
        if(seq[i].first+1==seq[i+1].first)
        {
            if(i+2<seq.size())
            {
                seq.insert(seq.begin()+i+1,{seq[i+2].first, 1});
                seq[i+3].second--;
                if(seq[i+3].second==0) seq.erase(seq.begin()+i+3);
            }
            else iter_swap(seq.begin()+i, seq.begin()+i+1);
        }
    }
    pair<int, int> t;
    for(int i=0;i<seq.size();i++)
    {
        t=seq[i];
        for(int j=0;j<t.second;j++) printf("%d ",t.first);
    }
    return 0;
}