djm03178   2년 전

아주 옛날에 적은 적이 있지만, 수십 페이지 뒤로 밀린지 오래라 주요 내용만 다시 적어보겠습니다. https://www.acmicpc.net/board/...

이 문제는 모든 입력을 배열이나 리스트에 저장해놓고 푸는 것이 의도된 문제가 아닙니다. 문제의 상단을 잘 보시면 메모리 제한은 겨우 8 MB이고 N은 최대 1000만인 것을 확인할 수 있습니다. 1000만 개의 수를 담는 데에는 C++ 기준으로 int로는 40 MB, short로는 20 MB가 필요하여 그 자체만으로도 메모리 제한을 초과합니다. 일부 언어는 보너스 메모리 제한 덕분에 입력이 다 받아지는 경우도 있지만, 의도된 풀이가 아니기 때문에 그로 인해 발생할 수 있는 다른 문제는 따로 적지 않겠습니다.

마찬가지로 문제를 푸는 어떠한 순간에도 N개의 독립된 원소를 어딘가에 전부 들고 있으면 메모리 초과로 곧바로 이어질 가능성이 높습니다. 또한 그렇기 때문에 일반적으로 정렬에 사용하는 merge sort, heap sort, quick sort 등이나 내장 정렬 함수 등도 전부 사용을 할 수 없습니다.

핵심은 입력으로 주어지는 수들이 전부 1만 이하라는 것입니다. 이를 어떻게 이용하면 이런 빠듯한 제한 내에서도 모든 수에 대한 정보를 저장하고 정렬된 상태로 출력까지 할 수 있을지 생각해 보세요. 모든 수를 개별적으로 저장하지 않아도 그에 대한 정보만 표현할 수 있으면 되고, 정렬을 실제로 하지 않아도 정렬된 상태로 출력만 할 수 있으면 된다는 것이 중요합니다.

또한 https://www.acmicpc.net/proble... 에 설명된 대로 빠른 입출력을 하지 않으면 그 때문에 시간 초과가 발생할 수도 있으니 꼭 확인해 보세요.

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