[BOJ/백준] 1071 소트

N = int(input())
arr = list(map(int,input().split()))
 
num_cnt = [0]*1005
 
for num in arr:
    num_cnt[num] += 1
 
 
cur = 0
result = []
while sum(num_cnt)>0:
    if num_cnt[cur]:
        if num_cnt[cur+1]:
            for next_num in range(cur+2,1001):
                if num_cnt[next_num]:
                    result.extend(num_cnt[cur]*[cur])
                    result.append(next_num)
                    num_cnt[cur] = 0
                    num_cnt[next_num] -= 1
                    break
            else:
                result.extend(num_cnt[cur+1]*[cur+1])
                result.extend(num_cnt[cur]*[cur])
                num_cnt[cur] = 0
                num_cnt[cur+1] = 0
 
        else:
            while num_cnt[cur]:
                result.append(cur)
                num_cnt[cur] -= 1
    cur += 1
 
print(*result)
 

 

플래티넘 문제로 어려웠던 문제였다. 

 

이 문제를 푸는 방법은 구분을 하는 것이다.

 

현재 숫자를 CUR이라고 하겠다. CUR+1의 숫자가 있는 경우와 없을때를 비교를 해서, 정렬을 해주면된다.

 

만약 CUR + 1의 숫자가 없을때에는 CUR의 값을 전부 출력시키면 된다.

 

 

그러나 CUR+1의 값이 존재할때는 2가지 경우가 있다.

 

CUR 보다 2이상 큰 값들이 존재하는지와 없는지 이다.

 

만약 없을때에는 CUR+1의 값들을 전부 출력한뒤에 CUR 값들을 출력시키면 된다.

 

그게 아니라 CUR보다 2이상 큰 값이 존재를 한다면,

 

CUR의 값들을 전부 출력시키고 그 다음에 CUR보다 2이상 큰 값을 한개 출력해주면 된다.

 

그러면 CUR과 CUR+1 사이에 CUR+2(이상)의 값이 들어가줘서 문제의 조건대로 출력이 가능해진다.