[Python] boj no. 1071 : 소트

Problem

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

Idea

오름차순으로 연속된 수가 없이 정렬해야 하는 문제이다. 기본적으로 사전순으로 정렬하므로 가장 낮은 수부터 다음과 같은 기준으로 정렬한다. 현재 정렬해야 할 숫자가 key라고 하면,

1. key+1이 존재하지 않으면 key를 모두 출력.
2. key+1이 존재할 때, key+1보다 큰 값이 존재하면 key를 모두 출력하고 key+2를 한번 출력.
3. key+1이 존재할 때, key+1보다 큰 값이 존재하지 않으면 key+1를 모두 출력한 뒤에 key를 모두 출력.

딕셔너리를 사용해 (숫자 번호 : 해당 숫자의 처리되지 않은 숫자의 갯수)의 형태로 구현하였다.

Code

import sys

def find_key(k):
    tar = 0
    
    for key, value, in match.items():
        if key > k+1 and value > 0:
            tar = key
            break
    
    return tar

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
numbers = sorted(numbers)
match = {}
for n in numbers:
    if match.get(n, False):
        match[n] += 1
    else:
        match[n] = 1

for key in match.keys():
    if match.get(key, 0) != 0:
        if match.get(key+1, 0) == 0: # not key+1 in match
            for _ in range(match[key]):
                print(key, end=" ")             
            match[key] = 0
        else:   # key+1 in match
            tar = find_key(key)
            if tar != 0:   # key+2~ in match
                for _ in range(match[key]):
                    print(key, end=" ")             
                match[key] = 0
                
                print(tar, end=" ")
                match[tar] -= 1
            else:               # not key+2~ in dict
                for _ in range(match[key+1]):
                    print(key+1, end=" ")             
                match[key+1] = 0
                
                for _ in range(match[key]):
                    print(key, end=" ")             
                match[key] = 0

Comment