djm03178   2년 전

  1. 모든 입력을 배열에 저장하면 당연히 메모리 초과입니다. 문제의 메모리 제한은 겨우 8MB입니다. 아무리 작은 자료형으로 저장한다고 해도 short형 (2바이트) 천만 개면 약 20MB로 역시 메모리 초과입니다. 입력을 전부 저장하지 않고 푸는 방법을 생각해 보세요. 힌트는 입력되는 정수의 범위에 있습니다.
  2. (C++) endl 쓰지 말고 '\n' 쓰세요. endl은 버퍼를 flush하기 때문에 매우, 매우, 매우 느립니다. 이건 이 문제 뿐만이 아니라 앞으로 푸실 모든 문제에 대해 공통입니다.
  3. int a[10000]; 의 원소는 9999까지입니다.
  4. 느린 입출력을 써도 시간 초과가 될 수 있습니다. https://www.acmicpc.net/proble... 에서 내가 충분히 빠른 입출력을 쓰고 있는지 확인해 보세요.
  5. Pypy를 쓸 경우 print가 아니라 sys.stdout.write를 해야 메모리 초과를 받지 않습니다.

통과는 됐는데 너무 느리다면 다음과 같은 이유가 있습니다.

  • 위의 1번의 경우 메모리 보너스가 있는 언어들에는 해당되지 않을 수 있습니다. 하지만 기본적으로 sort는 원소들의 비교를 통해 정렬을 수행하고, O(nlogn)의 시간복잡도를 가집니다. 천만 로그 천만은 2억 3천 정도로 상당히 무겁습니다. 애초에, 이 문제는 그렇게 풀라고 만든 문제가 아닙니다. 이런 식의 풀이를 허용할 거라면 굳이 메모리 제한을 넉넉하게 안 주고 8MB로 빡세게 할 필요가 없죠. 그럼 어떻게 할까요? 힌트는 사실 위에 3번에 있습니다.
  • O(nlogn)보다 빠르게 풀 수 있는데도 시간 제한이 3초씩이나 되는 건 바로 입력을 받는 것 자체가 그와 맞먹는 수준의 느린 속도를 자랑하기 때문입니다 (사실 입력량 자체가 O(nlog(최대자릿수))입니다). C++이라면 ios_base::sync_with_stdio(false); 를 하는 것만으로도 엄청난 속도의 향상을 볼 수 있고, Java라면 BufferedReader, Python에서는 sys.stdin.readline이 있습니다 (파이썬은 input()으로는 통과 자체를 못 하는 것으로 알고 있습니다). C 계열의 경우 fread나 mmap을 쓰면 정말 말도 안 되는 속도의 향상을 볼 수 있지만, 이건 해보고 싶은 사람만 해보면 됩니다.

bupjae   2년 전

"단계별로 풀어보기" (https://www.acmicpc.net/step/9) 를 통해 이 문제에 온 사람 중 일부가 radix sort 를 이용해 보려는 사례가 종종 발생합니다.

radix sort 는 어쨌든 모든 입력을 배열에 저장해야 하기 때문에 주어진 메모리 제한을 지킬 수 없습니다.

FAQ에 이 사항도 반영했으면 합니다.

djm03178   2년 전

추가했습니다.

jh05013   2년 전

파이썬으로는 메모리 제한으로 인해 단순 .sort로 풀 수 없습니다.

djm03178   2년 전

사실상 예외는 자바 뿐인가 보군요.

abel1802   2년 전

Java, Radix Sort를 통해서 해결하려고 머리 짜고 있었는데, 역시나였군요...

명쾌하게 정리해주셔서 감사합니다! 이제 다음 단계로 편하게 넘어갈 것 같네요.

혹시나 Java, Radix Sort 로 해결하신 분이 계신다면, 덧글을 통해서 알려주시길 바랍니다... 무척이나 궁금하네요...

rlarlgns25   2년 전

감사합니다!

skawngus11   1년 전

radix sort로 풀어보려했는데 왠지 안되더 군요. 감사합니다.

jh05013   1년 전

언제부터 그랬는지는 모르지만 단계별에서 기수 정렬에 대한 언급이 사라졌습니다.

esara2021   1년 전

pypy3로 하면 메모리 초과가 나오는 반면

python3로 하면 통과하네요.

FAQ 감사합니다!

jh05013   7달 전

Pypy를 쓸 경우 print가 아니라 sys.stdout.write를 해야 메모리 초과를 받지 않습니다.

추가해 주세요.

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