[Python] 백준 #10989 수 정렬하기 3

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

이 문제 이름을 보면 알겠지만.. 같은 문제가 메모리와 시간초과 제한만 다르게 출제되어있다.

1과 2는 sorted 내장 함수와 다른 정렬 알고리즘을 이용하여 쉽게 풀었지만,

이번 문제는 시간제한과 메모리 제한이 다음과 같다.

3 초 (하단 참고)

8 MB (하단 참고)

입력개수 N(1 ≤ N ≤ 10,000,000)로 주어져있고, 입력 수는 10,000보다 작거나 같은 자연수인 것에 비해 메모리 제한이 너무 작아서 4번이나 메모리 초과 메시지를 받고.. (이 문제가 정답률이 20%인 이유가 있음)

뭐가 있을까 생각하다가 평생 쓸일이 없을 줄 알았던, counting sort 를 이용하여 해결하였다.

 

#카운팅 sort
import sys

n=int(sys.stdin.readline())
cnt=[0]*10001

List=[]
for i in range(n):
    List.append(int(sys.stdin.readline()))

for i in List:
    cnt[i]+=1

for i in range(1,10001):
    for j in range(cnt[i]):
        print(i)
            

처음엔 이 처럼 배열에 따로 받아서 counting을 해주었는데,

역시나 리스트는 따로 메모리 공간을 사용하기 때문에 메모리 초과가 발생했고

 

아래와 같이, cnt 리스트 하나만을 이용하여 문제를 해결했다!

#카운팅 sort
import sys

n=int(sys.stdin.readline())
cnt=[0]*10001

for i in range(n):
    cnt[int(sys.stdin.readline())]+=1

for i in range(1,10001):
    for j in range(cnt[i]):
        print(i)
            

메모리 29584 KB

시간 9732 ms