jyc4836   2년 전

잘 돌아가는 알고리즘인데 채점해 보니 메모리 초과가 나서 질문 게시판부터 보니 https://www.acmicpc.net/board/...에 이렇게 돼있네요.

  1. 모든 입력을 배열에 저장하면 당연히 메모리 초과입니다. 문제의 메모리 제한은 겨우 8MB입니다. 아무리 작은 자료형으로 저장한다고 해도 short형 (2바이트) 천만 개면 약 20MB로 역시 메모리 초과입니다.
  2. (C++) endl 쓰지 말고 '\n' 쓰세요. endl은 버퍼를 flush하기 때문에 매우, 매우, 매우 느립니다. 이건 이 문제 뿐만이 아니라 앞으로 푸실 모든 문제에 대해 공통입니다.
  3. int a[10000]; 의 원소는 9999까지입니다.
  4. 단계별로 풀어보기에서 이 문제를 기수 정렬 (radix sort)로 풀어보자고 되어 있지만, 실제로는 메모리 보너스 없이는 할 수 없습니다. 수정 요청이 이전에도 있었지만, 단계별로 풀어보기 자체가 개편될 예정이기 때문에 수정되지 않은 것 같습니다.

게다가 기수 정렬은 공간이 두 배로 필요한데 4번 문장 따르면 그냥 카운팅 소트밖에 못 쓰는 건가요?

jyc4836   2년 전

하 열심히 짜 놓은 거 다 날려버리고 새로 만들어야겠네요

감사합니다

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