[Python/파이썬] 백준 알고리즘 10989번 / 수 정렬하기 3

[Python/파이썬] 백준 알고리즘 10989번 / 수 정렬하기 3

 

문제 링크:https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

---

최종 소스코드

 

import sys
N = int(input())
S = [0] * 10001
for i in range(N):
    a = int(sys.stdin.readline())
    S[a] += 1
for i in range(10001):
    if S[i] != 0:
        for j in range(S[i]):
            print(i)

 

---

<풀이>

언뜻 쉬워보이지만 정답률이 23%인 것을보고 쉬운 방법으로는 풀리지 않겠구나 생각이 들었다. 역시나 append와 sort 함수를 이용해서 풀면 시간초과, 메모리 초과 콤보를 맞게 된다. 구글링을 해보고 이 문제는 계수정렬을 이용해 풀어야 한다는 것을 알 수 있었다.

 

1. input VS sys.stdin.readline()

for i in range(N):
    a = int(sys.stdin.readline())

백준을 풀다보면 input으로 풀면 시간 초과로 나오지만 sys.stdin.readline으로 풀면 풀리는 경우가 더러 있다. input과  sys.stdin.readline의 차이는 (1) input() 내장 함수는 parameter로 promt message를 받을 수 있기 때문에 이 출력 여부로 인해 시간이 딜레이 된다. (2) input() 내장 함수는 입력받은 값의 개행문자를 삭제시켜 반환한다. 이런 차이로 백준을 풀때 특히 '입력이 자주 반복될 경우'에 input() 대신 sys.stdin.readline을 쓰면 시간 초과 문제를 해결할 수 있다.

 

2. 계수정렬

S = [0] * 10001
for i in range(N):
    a = int(sys.stdin.readline())
    S[a] += 1

최대 10000000개인 N개의 숫자를 모두 일일히 for 구문으로 append 해서 추가하면 메모리를 과도하게 사용한다. 이를 위해 쓸 수 있는 방법이 계수정렬이다. 숫자의 최대 수가 10000이므로 0~10000까지의 값이 0인 리스트를 만든다. 이 후 만약 숫자가 12라면 S[12]에 1을 더한다.

 

3. 출력

for i in range(10001):
    if S[i] != 0:
        for j in range(S[i]):
            print(i)

이 후 S를 S[0]부터 탐색하여 값이 0이 아니라면 숫자를 출력한다. 이 때 S[2]가 2라면 2번 출력 4라면 4번 출력된다. 이렇게 하면 자연스럽게 오름차순으로 정리가 되고 중복 숫자도 처리된다.