따로따로 포스팅하긴 귀찮으니 수 정렬하기 시리즈 세 문제를 한번에 정리하도록 하겠다.

문제

수 정렬하기 1

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	203641	116491	80062	58.099%

문제 설명

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

---

수 정렬하기 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	314436	95439	66693	31.135%

문제 설명

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

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

---

수 정렬하기 3

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
5 초 (하단 참고)	8 MB (하단 참고)	288115	68346	52264	23.755%

문제 설명

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

입력

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

출력

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

---

내 풀이(수 정렬하기)

n = int(input())
num = []
for _ in range(n):
    num.append(int(input()))
num.sort()
for i in num:
    print(i)

sort() 함수를 사용하여 리스트 값을 정렬해주었다.

---

내 풀이(수 정렬하기2)

import sys
input = sys.stdin.readline

n = int(input())
num = []
for _ in range(n):
    num.append(int(input()))
num.sort()
for i in num:
    print(i)

수 정렬하기와 수 정렬하기2 문제의 차이는 N의 개수 범위와 시간 초과 제한이다.
N의 개수가 많아질수록 sort() 처리과정에서의 시간이 증가하는데,
2번 문제에서는 1번 문제에서 입력값을 sys 라이브러리를 활용해 처리하기만 해도
시간초과를 막을 수 있다.

---

내 풀이(수 정렬하기3)

import sys
input = sys.stdin.readline

n = int(input())
num = [0] * 10001 # 10000개까지 입력값을 받을 수 있음(인덱스 값 0부터 10000까지)
# 각 인덱스에 맞는 값이 등장하면 += 1씩 해줌

for _ in range(n):
    num[int(input())] += 1 # 1이 등장하면 num[1] 값에 += 1
for i in range(10001):
    if num[i] != 0:
        for j in range(num[i]):
            print(i) # 인덱스 값에 따라 반복출력

이 문제는 앞전 문제들보다 N의 개수 범위가 훨씬 넓고,
메모리 제한도 (128, 256MB)인 두 문제에 비해 8MB로 턱없이 부족하다.

대신 시간 제한이 5초이므로 메모리 제한에 초점을 맞추면 된다.

이 문제는 메모리를 줄이기 위해 앞전 문제들처럼 리스트에 모든 n을 append를 해주지 않고
리스트에 미리 메모리를 할당해주었다.
num = [0] * 10001

이때 수의 범위가 1에서 10000 사이의 자연수이므로, 리스트의 인덱스를 10001까지로 설정해
인덱스 값 += 1 로 해당 숫자의 개수를 세는 for문을 구현하였다.

이는 초기 DP 테이블을 만드는 방식과 동일하다.