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. 최종 수열을 출력한다.
오늘의 교훈) 그리디 알고리즘은 재미있다.