BOJ 1071 - 소트

문제

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

 

 

풀이

그리디 문제다

사전 순으로 가장 앞선 것을 출력하기 위해 배열이 오름차순으로 정렬되어야 한다

이를 위해 계수정렬을 통해 배열을 정렬한다

 

다음 규칙을 적용한다

a[i] 값에 대하여

1. a[i] + 1 값이 배열에 존재하면

1-1. a[i] + 2 이상의 값 k가 배열 안에 존재하면, a[i] 값을 전부 출력하고 k를 출력한다

1-2. a[i] + 2 이상의 값이 배열 안에 존재하지 않으면, a[i] + 1 값을 한번 출력한다

 

2. a[i] + 1 값의 배열에 존재하지 않는다면 a[i] 값을 전부 출력한다

 

 

코드

python

n = int(input())
nums = [int(x) for x in input().split()]
 
csort = [0 for i in range(1002)]
for i in range(n):
    csort[nums[i]] += 1
 
answer = ""
 
while True:
    is_empty_csort = True
    for i in range(1001):
        if csort[i]:
            is_empty_csort = False
            if csort[i + 1]:
                k = -1
                for j in range(i + 2, 1001):
                    if csort[j]:
                        k = j
                        break
                if k != -1:
                    while csort[i]:
                        answer += str(i) + " "
                        csort[i] -= 1
                    answer += str(k) + " "
                    csort[k] -= 1
                    break
                else:
                    answer += str(i + 1) + " "
                    csort[i + 1] -= 1
                    break
            else:
                while csort[i]:
                    answer += str(i) + " "
                    csort[i] -= 1
                break
 
    if is_empty_csort:
        break
 
 
print(answer)