BaekJoon 10989번: 수 정렬하기 3 (Python)

---

1. Problem

---

2. Solution

import sys

N = int(input())
arr = [0] * 10001  # 0으로 채워진 길이 10001의 list 생성

# readline()으로 숫자를 읽어 숫자에 해당하는 list의 index의 값에 1씩 더한다.
for i in range(N):
    arr[int(sys.stdin.readline())] += 1

for i in range(10001):  # 0 ~ 10000까지 반복
    if arr[i] != 0:  # 만약 arr list의 index i의 값이 0이 아니면
        for j in range(arr[i]):  # arr list의 index i의 값만큼 i 반복 출력
            print(i)

---

3. Detail

실패 Code - 메모리 초과

import sys

N = int(input())
array = list(int(sys.stdin.readline()) for _ in range(N))
array.sort()
print(*array)

수를 정렬하는 문제라 계속 .sort()를 사용해서 시간초과만을 고려하며 문제를 풀었는데 메모리 초과가 나와서 당황했다. 이 문제는 .sort()를 이용하여 정렬로 문제를 풀면 메모리가 8MB로 매우 작게 제한되어 있기 때문에 무조건 메모리 초과가 발생한다. 결과적으로 이 문제는 .sort()를 사용하지 않고 문제를 풀어야 한다는 것을 알 수 있다.

N = int(input())
arr = [0] * 10001

먼저 첫번 째 줄의 입력 N을 int(input())으로 받고, [0] * 10001로 0으로 채워진 길이 10001의 arr 리스트를 생성한다. 리스트의 길이는 index 0의 값은 사용하지는 않지만 편의상 0 ~ 10000까지인 10001로 설정한다.

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

그 후 int(sys.stdin.readline())으로 두번 째 줄부터 N + 1번 째 줄까지의 수를 for문을 통해 반복적으로 받는다. 이 때 int(sys.stdin.readline())에 해당하는 수와 같은 arr 리스트의 위치의 값에 1씩 더해지도록 한다. 위의 for문이 종료되면 arr 리스트 안에는 입력된 수들의 index 위치에 해당 숫자가 입력된 횟수에 대한 정보가 담기게 된다.

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

arr 리스트에 정보를 담은 후에는 위의 code를 통해 결과를 출력하게 된다. 이 때 arr 리스트의 길이만큼 i가 0 ~ 10000까지 for문을 통해 반복하게하고, arr[i]에 해당하는 값이 0이 아닌 경우에만 arr[i] 값 만큼 i를 반복 출력하면 원하는 출력이 나오게 된다.

---