길이 N의 수열에 대해 우선 K개의 세트에 대해 정렬을 완료했다고 합시다.

그런데 그 다음 세트에서 N번째 수(맨 끝 수)까지 정렬하라고 한다면, 이전 과정의 정렬 결과가 의미가 없어집니다.

이 사실을 잘 이용하면 O(N log N)에 해결 가능합니다.

제가 그 방법도 생각 했는데 만약 K 가 10만 이고

100000 100000

99999 99999

99998 98888

.

.

.

1 1

이런식으로 들어오면 의미 없지 않나요??ㅜㅜ 아니면 제가 이해를 잘못 한건가요?

그 예시에서 10만 번째 수는 첫 정렬 후에는 더 이상 정렬되지 않습니다.

따라서 10만 번째 수는 첫 번째 세트, 99999번째 수는 두 번째 세트, ... 이런식으로 정렬되므로

수열의 마지막 수부터 역추적해나가면 됩니다.

처음에 정렬된 배열에서, 마지막 수가 오름차순 정렬된 수인지, 내림차순 정렬된 수인지, 정렬되지 않은 수인지 입력을 통해 알아낸 다음

마지막 수부터 결정해나가면 됩니다.

참고로 저는 정렬된 배열을 유지하기 위해 수의 삽입, 삭제, 탐색을 O(log N) 에 할 수 있는 STL의 multiset을 사용했습니다.

감사합니다ㅎㅎ

아직 완벽하게 이해는 되지않았지만 좀 더 생각 해보겠습니다.

정말로 감사 합니다.