hj_d   3년 전

이 문제를 푸려고 하는데 접근 방법 조차 생각이 나지 않네요.

규칙을 찾으려고 했는데도 못찾겠고, 하나하나 다하면 당연히 시간 초과 이고,

어떤 알고리즘이 있는건가요? 힌트좀 주세요 ㅜㅜ

jjwdi0   3년 전

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

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

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

hj_d   3년 전

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

100000 100000

99999 99999

99998 98888

.

.

.

1 1

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

jjwdi0   3년 전

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

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

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

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

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

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

hj_d   3년 전

감사합니다ㅎㅎ

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

정말로 감사 합니다.

댓글을 작성하려면 로그인해야 합니다.