백준 1071, 소트

개요

문제 링크
플래 5, Greedy
a[i+1] != a[i]+1이면서 사전순으로 가장 앞서게 정렬하기

---

접근

1. 그리디한 인간이 되자. 수를 꺼내서 출력한다고 생각할 때,
   1. 가장 작은수부터 꺼내는 것이 가장 유리하다. 이 수를 X라고 해보자.
   2. 꺼낼 수 없는 첫 번째 경우. X가 (이전 수)+1인 경우에는 X+1부터 시작되는 최솟값을 다시 구한다. 이게 왜 되느냐? X보다 작은 수는 없다. 그러면 다음 최선 선택지는 항상 X보다 크다.
   3. 꺼낼 수 없는 두 번째 경우이자 이 문제의 핵심. X와 X+1만 남은 경우이다. 예를들어 2,2,3,3만 남은 경우 2를 먼저 뽑을 수 없다. 어떻게 뽑아도 2뒤에 3이 오는 경우가 생긴다.
   4. 그럼 두 번째 경우를 커버하기 위해 X+1부터 최솟값을 구한다. 그 값을 T라 했을 때, 만약 T가 존재하고, X+2 부터 끝까지 어떤 수도 존재하지 않으면? 그때는 무조건 T를 뽑아야 한다. 즉 2233에서 3을 뽑아야만 하는 경우가 된다.
   5. 이때 존재하지 않음을 확인하는 함수를 따로 짜도 되지만, X+2부터 최솟값을 구해줘서 단순화해도 된다.
2. map을 쓰려다가 크기 1000짜리 배열을 사용했다. 나머지는 이전 수를 저장해주면서 진행하면 크게 어렵지 않다.

---

Pseudo code

while(n)
    X = min_start(0)
    if (X = H+1)
        X = min_start(X+1)
    else
        T = min_start(X+1)
        if (T && min_start(X+2) == 0)
            X = T
    count[X]--

Source code

#include <iostream>
using namespace std;

#define M 1000
int g[M+1];

int min(int s) {
    for (int i=s;i<=M;i++)
        if (g[i])
            return i;
    return 0;
}

int main() {
    int n,x;
    cin>>n;
    for (int i=0; i<n; i++)
        cin>>x,g[x]++;
    int m,t,h=-2;
    while(n--) {
        m = min(0);
        if (m==h+1)
            m = min(m+1);
        else {
            t = min(m+1);
            if (t&&!min(m+2)) m = t;
        }
        h = m;
        cout<<m<<" ",g[m]--;
    }
}