15. Python(수 정렬하기(심화))

[toc]

수 정렬하기(심화)

문제

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

---

제출(오답)

코드1 - 메모리 초과

import sys
import heapq

n = int(sys.stdin.readline().strip())
min_heap = []

for _ in range(n):
    n_lst = int(sys.stdin.readline().strip())
    heapq.heappush(min_heap, n_lst)

while min_heap:
    print(heapq.heappop(min_heap))

# 입력
10
5
2
3
1
4
2
3
5
1
7

# 출력
1
1
2
2
3
3
4
5
5
7

---

오답 풀이

1. 틀린 이유

• 한 가지 조건을 보지 못하고 코드를 작성함

“첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. “

• 그리고 메모리 제한도 8 MB로 N개의 최대값인 10,000,000개를 모두 저장해선 안 됨
  • 그말은 즉, sort와 sorted를 사용할 수 없다는 뜻

2. 다른 방법 생각

1) 리스트 사용

import sys

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

• 우선 최대 10,000개의 수가 들어갈 수 있다는 조건을 보고 리스트 크기를 10,001로 설정

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

• 이후 n개의 숫자를 입력받는데, 받으면서 n_lst에 입력한 인덱스에 1씩 더함
  • 중복되는 숫자도 포함시키기 위함

2) 출력

for i in range(10001):
    if n_lst[i] != 0:
        for j in range(n_lst[i]): ## 중복된 수 누락 방지
            print(i)

• for i in range(10001):는 1부터 10,000까지 각 숫자를 순서대로 확인함
• 만약 n_lst[i]가 0이 아니라면, i가 n_lst[i]번 등장했다는 의미이므로 for j in range(n_lst[i])를 통해 i를 n_lst[i]번 반복 출력함
• 이렇게 하면 각 숫자가 등장한 횟수만큼 출력되어 중복된 숫자도 누락 없이 출력됨

---

제출(정답)

코드2

import sys

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

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

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