백준 10989번- '수 정렬하기 3' (PYTHON 풀이)

문제:

 

문제 이해는 어렵지 않다. 사용자로부터 입력을 받고 해당 입력값을 오름차순으로 정렬한 것을 한줄씩 출력해주면 된다.

 

풀이:

N = int(input())
li = []

for i in range(N):
    li.append(int(input()))
sort = sorted(li)
for i in sort:
    print(i)

첫 시도의 코드이다. '왜 이게 높은 단계의 문제이지? 어제 푼 문제랑 다를 바 없는데?' 라고 생각했는데 역시 호락호락하지 않다.

이렇게 풀면 메모리초과 에러가 뜬다. 메모리 제한은 8MB인데 O(n)만큼의 복잡도를 가지고 있고 수를 많이 받고 있다. 또한 for문에서 append를 쓰면 메모리 재할당 문제가 있어 메모리초과가 일어난다고 한다.

import sys

N = int(input())
li = []

for i in range(N):
    k = int(sys.stdin.readline())
    li.append(k)
sort = sorted(li)

for i in sort:
    print(i)

두번째 시도로, 혹시 몰라 import sys를 사용했다. 예전에 문제를 풀 때 이 코드만으로 해결됐던 적이 있어 시도하였는데 메모리 부분이라 그런지 효과가 없었다. 결국 어떻게 해결하면 될지 모르겠어서 구글링을 하였다.

import sys

N = int(sys.stdin.readline())
li = [0] * 10001

for q in range(N):
    li[int(sys.stdin.readline())] += 1

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

일단 두번째 버전이랑 똑같이 sys 라이브러리를 import해주고 리스트 값을 지정받는다. 이 과정을 통해 10001번째 자리의 0이 들어간 리스트가 생성된다.

(li = [0,0,0,...] -> 이런 식으로 0번째부터 10001번째까지 0이 들어간 리스트 생성)

 

그 후 입력받은 수에 해당하는 리스트 각 자리에 1을 더해주고 그 횟수만큼 출력해주면 된다. 계수 출력 방식이라고 하는 것 같은데 너무 신박한 방법이다.. 파이썬의 장점이 내장된 함수가 간편하고 쉬운 게 많다는 점인데 이번 문제처럼 sort, append와 같이 무거운 함수가 메모리를 크게 잡아먹는다면 문제가 많을테니.. 오늘 문제랑 비슷한 공부를 하면 좋겠다는 생각을 했다.