백준 1071번 소트

http://icpc.me/1071

1071번: 소트

풀이

간단한 그리디 문제입니다.

사전순으로 앞선 배열을 만들어야 하기 때문에 앞에서 최대한 작은 수를 사용해야 합니다.

앞서 $i$개의 수를 최적으로 출력했다고 가정할 때 가능하다면 무조건 출력하지 않은 수 중 최솟값을 출력해야 하며, 최솟값을 출력할 수 없다면 두 번째로 작은 값을 출력해야 합니다. 최솟값을 출력할 수 없는 경우는 두 가지입니다.

 

1) $i$번째로 출력한 수 + 1 == 최솟값일 때

2) 출력하지 않은 수에서 중복을 제거하면 두 개의 수만 남을 때

 

1번 경우는 문제의 조건과 같으며, 2번 경우는 문제의 두 번째 예제에서 확인할 수 있습니다. 

배열을 비내림차순으로 정렬했을 때 인접한 두 원소의 차가 1이라면 둘 사이에 다음으로 작은 값을 하나 끼워넣는다고 생각할 수도 있습니다. 2번 경우에는 끼워넣을 값이 없기 때문에 부득이하게 큰 값을 먼저 모두 출력하고 작은 값들을 출력해야 합니다.

 

위 과정을 $N$번 반복하면 정답을 구할 수 있습니다.

 

코드

다양한 방법으로 구현할 수 있습니다.

저는 우선순위 큐를 사용하여 구현했습니다.

시간복잡도는 $O(NlogN)$입니다.

 

 

사족

N제한이 매우 작은데 왜 그런지는 잘 모르겠습니다. 

덕분에 백트래킹으로도 풀 수 있다고 합니다.

잘만 구현한다면 $O(N)$ 시간복잡도로도 풀 수 있을 것 같습니다.