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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

입출력 예

 

제출 코드

import sys
n = int(input())
lst = [0 for i in range(10000)]
for i in range(n):
    x = int(sys.stdin.readline())
    lst[x-1] += 1
for idx, cnt in enumerate(lst):
    if cnt != 0:
        for i in range(cnt):
            sys.stdout.write('{}\n'.format(idx+1))

상당히 애를 먹었던 문제인데, 핵심은 메모리도, 시간도 초과하지 않아야 한다는 것이다. 정말 아주 간단하게 구현한다면 입력받는 값들을 리스트에 넣고 정렬하고 출력하는 로직으로 짤 수 있겠지만 그렇게 된다면 시간이 많이 초과하게 될 것이다. 아무튼 라인 바이 라인으로 설명을 해놔야 까먹지 않을 것 같다.

 

(1) line 1

입력값과 출력값으로 올 수 있는 최대값이 너무나도 크기 때문에 시간 초과를 방지하기 위해 sys모듈을 import한다. 해당 모듈의 stdin.readline() 함수와 stdout.write() 함수를 써서 효율을 증대시켜야 한다.

 

(2) line 3

이 문제의 핵심이 될 것 같은데 미리 리스트를 선언해주면서 0이라는 원소를 10,000개 채워 넣어주며 초기화시켜준다. append를 하면 시간이 초과되므로 미리 선언해놓은 list의 인덱스를 통해 값에 바로 접근해야 한다!

 

여기서 원소가 10,000개인 이유는? 입력값으로 주어지는 숫자들이 1 이상 10,000 이하에 있는 값이라 리스트의 각 인덱스가 숫자 하나하나의 등장 횟수를 의미하게 선언하면 되기 때문이다.

 

(3) line 4 ~ 6

입력값을 읽으며 각 숫자의 등장 횟수를 카운팅해준다.

 

(4) 7 ~ 10

만약 한 번도 등장하지 않아 초반에 선언했던 0이 그대로 남아있는 원소는 생략하고, 카운팅되어 있는 숫자들을 오름차순으로 출력한다. 이렇게 특정 숫자를 출력할 때는 해당 숫자의 등장 횟수만큼 출력을 반복한다.

 

실패 기록

import sys

n = int(input())
dic = {}

for i in range(n):
    x = int(sys.stdin.readline())
    dic[x] = dic.get(x, 0) + 1

for lst in sorted(dic.items()):
    for i in range(lst[1]):
        sys.stdout.write('{}\n'.format(lst[0]))

이 코드는 처음에 생각하여 제출했던 코드인데 PyPy3로 제출하면 메모리 초과, Python3로 제출하면 시간 초과다. 시간 복잡도가 나빠보이지 않는데 많이 나쁜가 보다... 추후에 해당 코드의 시간복잡도를 뜯어봐야겠다. 

 

아래는 계속 초과해서 너무 마음이 아팠던 장면인데, 그냥... 박제해버리자. 다음부터 이런 슬픔은 덜 겪고 싶다ㅠㅠ

 

 

 

 

Source : https://www.acmicpc.net/problem/10989