BOJ 1071 - 소트 링크
(2023.09.12 기준 P5)

문제

N개의 정수가 주어진다. 연속된 두 수가 연속된 값이 아니게끔 사전순으로 가장 앞서게 정렬한 것을 출력

알고리즘

그리디

풀이

먼저, Counting Array를 만들자. 그렇게 해야 남은 수의 개수를 파악하기 쉬우며, 제외하기에도 용이하다.

이제부터 가장 작은 세 수를 찾으면서 출력시키고 제외할 것이다.


1. 만약 찾은 수가 하나라면?

• 찾은 수의 개수만큼 전부 출력 후 종료하면 된다. 더 이상 수가 남지 않기 때문.
  
  

2. 만약 찾은 수가 둘이라면?

• 찾은 두 수가 연속되는 관계라면 두번째, 첫번째 순으로. 아니면 첫번째, 두번째 순으로 개수만큼 전부 출력 후 종료하면 된다. 마찬가지로 더 이상 수가 남지 않기 때문에 바로 종료하자.
  
  

3. 만약 찾은 수가 셋이라면?

• 먼저, 첫번째 수를 개수만큼 전부 출력하자.
  그리고 만약에 첫번째와 두번째 수가 연속되는 관계라면? 세번째 수 하나를 출력하면, 앞으로 출력되는 수가 조건에 위반되지 않게 된다. 그리고 다시 세 수 찾기를 반복하면 된다.

어차피 사전순으로 가장 앞서는 것을 찾아야 하기 때문에, 찾은 수가 둘인 특수한 경우를 제외하면 무조건 첫번째 수가 앞으로 가야 사전순으로 가장 앞서게 된다. 그러므로 세 경우에 따라 매 순간의 최적해를 찾으면 문제에 대한 최적해가 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    // Counting Array 만들기
    int ct[1001]; fill(ct, ct + 1001, 0);
    for (auto a: A) ct[a]++;

    int st = 0, en = 0; // 탐색 시작 지점, 탐색 끝 지점
    for (int i = 0; i < N; i++) en = max(en, A[i]);
    vector<int> find;
    while (true){

        // 최대 3개의 연속되는 수를 찾는다.
        find.clear();
        for (int i = st; i <= en; i++) if (ct[i]){
            find.push_back(i);
            if (find.size() == 3) break;
        }

        // 1개를 찾았다면 찾은 수를 개수만큼 출력 후 종료
        if (find.size() == 1){
            while (ct[find[0]]--) cout << find[0] << ' ';
            break;
        }

        // 2개를 찾았다면
        else if (find.size() == 2){
            if (find[0] + 1 == find[1]){ // 연속되는 관계라면 두번째 수, 첫번째 수 순으로 개수만큼 출력 후 종료
                while (ct[find[1]]--) cout << find[1] << ' ';
                while (ct[find[0]]--) cout << find[0] << ' ';
            }
            else{ // 연속되지 않는다면 첫번째 수, 두번째 수 순으로 개수만큼 출력 후 종료
                while (ct[find[0]]--) cout << find[0] << ' ';
                while (ct[find[1]]--) cout << find[1] << ' ';
            }
            break;
        }

        // 3개를 찾았다면 첫번째 수 전부 출력
        else{
            while (ct[find[0]]--) cout << find[0] << ' ';
            st = find[1]; // 시작 지점은 두번째 수부터 시작

            // 만약 첫번째 수와 두번째 수가 연속되면
            // 연속되는 경우를 방지하기 위해 세번째 수 하나 출력
            if (find[0] + 1 == find[1]){
                cout << find[2] << ' ';
                ct[find[2]]--;
            }
        }
    }
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

# Counting Array 만들기
ct = [0] * 1001
for a in A:
    ct[a] += 1

st = 0 # 탐색 시작 지점
en = max(A) # 탐색 끝 지점
while True:

    # 최대 3개의 연속되는 수를 찾는다.
    find = []
    for i in range(st, en + 1):
        if ct[i]:
            find.append(i)
            if len(find) == 3:
                break

    # 1개를 찾았다면 찾은 수를 개수만큼 출력 후 종료
    if len(find) == 1:
        for _ in range(ct[find[0]]):
            print(find[0], end = ' ')
        break

    # 2개를 찾았다면
    elif len(find) == 2:
        if find[0] + 1 == find[1]: # 연속되는 관계라면 두번째 수, 첫번째 수 순으로 개수만큼 출력 후 종료
            for _ in range(ct[find[1]]):
                print(find[1], end = ' ')
            for _ in range(ct[find[0]]):
                print(find[0], end = ' ')
        else: # 연속되지 않는다면 첫번째 수, 두번째 수 순으로 개수만큼 출력 후 종료
            for _ in range(ct[find[0]]):
                print(find[0], end = ' ')
            for _ in range(ct[find[1]]):
                print(find[1], end = ' ')
        break

    # 3개를 찾았다면 첫번째 수 전부 출력
    else:
        for _ in range(ct[find[0]]):
            print(find[0], end = ' ')
        ct[find[0]] = 0
        st = find[1] # 시작 지점은 두번째 수부터 시작

        # 만약 첫번째 수와 두번째 수가 연속되면
        # 연속되는 경우를 방지하기 위해 세번째 수 하나 출력
        if find[0] + 1 == find[1]:
            print(find[2], end = ' ')
            ct[find[2]] -= 1