[백준 1071번] 소트 (Python3)

import sys
input = sys.stdin.readline

N = int(input())
A = [*map(int,input().split())]

A.sort()

cntlist = {}
for a in A:
  if cntlist.get(a):
    cntlist[a] += 1
  else:
    cntlist[a] = 1

numlist = sorted(cntlist)
N = len(numlist)
seq = []
for i in range(N):
  n = numlist[i]
  if not cntlist[n]:
    continue
  if i == N-1:
    for _ in range(cntlist[n]):
      seq.append(n)
    break
  if numlist[i+1]==n+1:
    if i==N-2:
      for _ in range(cntlist[n+1]):
        seq.append(n+1)
      for _ in range(cntlist[n]):
        seq.append(n)
      break
    for _ in range(cntlist[n]):
      seq.append(n)
    if cntlist[numlist[i+1]]:
      seq.append(numlist[i+2])
      cntlist[numlist[i+2]] -= 1
  else:
    for _ in range(cntlist[n]):
      seq.append(n)

print(*seq)

그리디 알고리즘 문제이다.

아이디어를 떠올리기는 매우 쉽지만, 조건분기를 나누는게 살짝 까다로울 수 있다.

 

알고리즘을 요약하면,

1. N개의 정수를 오름차순으로 정렬하여 numlist에 담고, 각 숫자들의 개수를 저장한다.

2. numlist의 숫자들에 대해 for문을 돌려가며 seq에 스택을 쌓아준다.

3. 스택을 쌓을 때, 현재의 번호 i에 대해서 i+1이 마지막이고, i+1의 숫자가 현재의 숫자보다 1 크다면, i+1의 숫자들을 전부 seq에 먼저 넣고 현재의 숫자를 넣는다.

4. 3번에 해당하지 않는 경우 현재의 번호의 숫자들을 일단 전부 넣는다.

5. 만약 i+1의 숫자가 현재의 숫자보다 1 더 크다면 i+2의 숫자를 1개 먼저 넣는다. (이때 i+1의 숫자의 개수가 0개라면 넣지 않는다)

6. 최종 수열을 출력한다.

 

 

오늘의 교훈) 그리디 알고리즘은 재미있다.