bupjae   3년 전

단계별로 풀어보기 -> 9단계 (정렬) -> 3단계 (10989번, 수 정렬하기 3) 에 따르면 이 문제는 카운팅 정렬(Counting Sort) 혹은 기수 정렬(Radix Sort) 로 풀 수 있다고 되어있습니다.


그런데 기수 정렬의 공간복잡도는 O(w+n) 으로, 주어진 입력 데이터 10,000,000개를 각각 1byte 크기로 저장한다고 가정해도 9.5MB로, 문제에서 주어진 메모리 제한 8MB 를 초과합니다.


카운팅 정렬로는 주어진 시간과 메모리로 충분히 풀 수 있긴 합니다.


이 문제의 출제 의도가 정말로 기수 정렬를 사용하는 것인지 확인 부탁드립니다.

djm03178   3년 전

아마 문제를 처음 만들 때 의도에는 기수 정렬도 있지 않았을까 싶긴 한데... 메모리 제한이 들어갔기 때문에 아마 불가능하다고 보이네요. 단계별로 풀어보기에 넣을 때 이를 고려하지 못했던 것이 아닌가 싶습니다.

다만 메모리 보너스가 붙는 언어들이라면 가능할 수도 있겠네요.

bupjae   1년 전

"단계별로 풀어보기" 에서 기수 정렬 에 대한 언급이 삭제된 것을 확인했습니다.

이 요청은 해결된 것으로 생각해도 될 것 같습니다.

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