[백준/1071] 소트 (Python)

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

1071번: 소트

Difficulty : Platinum 5

 

Status : Solved

 

Time : 01:38:20

 

 

---

 

문제 설명

 

 

N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. N개의 수는 1,000보다 작거나 같은 자연수 또는 0이다.

 

출력

 

첫째 줄에 문제의 정답을 출력한다.

 

입력 예시

 

3
1 2 3

 

출력 예시

 

1 3 2

 

 

---

 

풀이

 

많이 헤맸던 문제. 그리디하게 풀었다.

 

num[i] + 1 = num[i+1]를 만족시키는 i+1이 없는 경우, 그대로 모든 num[i]를 출력하면 된다.

 

문제는 존재할 경우. 존재할 경우는 num[i+1]를 초과하는 최솟값 num[j] 여부를 조사하도록 한다.

 

• 만약 존재한다면, num[i]를 그대로 출력하고, 그 다음에 num[j]를 하나 끼워넣는다. 그리고 num[i+1]로 넘어간다. 만약 j == i+2라고 해도, 재귀적으로 num[i+1] 케이스에서 해결될 것이다.
• 만약 존재하지 않는다면, 이 수열의 최댓값은 num[i+1]이 된다. 즉 모든 num[i+1]을 모두 출력하고 그 다음 num[i]를 출력하면 된다.

 

풀이 코드

from collections import Counter
Max = 1001
N = int(input())

num_maps = [0]*Max
for key, val in  Counter(map(int, input().split())).items() :
  num_maps[key] = val

ans = list()
for i in range(Max) :
  if not num_maps[i] :
    continue
  if i == Max-1 or i < Max-1 and not num_maps[i+1] :
    ans += [i]*num_maps[i]
    continue
  if i < Max-2 :
    best_idx = -1
    for j in range(i+2, Max) :
      if num_maps[j] :
        best_idx = j
        break
    if best_idx != -1 :
      ans += [i]*num_maps[i] + [best_idx]
      num_maps[best_idx] -= 1
    else :
      ans += [i+1]*num_maps[i+1] + [i]*num_maps[i]
      num_maps[i+1] = 0
  else :
    ans += [i+1]*num_maps[i+1] + [i]*num_maps[i]
    num_maps[i+1] = 0

print(*ans)

풀이 완료!