[백준] 10989번(브론즈1) : 수 정렬하기3 (python 파이썬)

10989번(브론즈1) : 수 정렬하기3

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

수 정렬하기 3

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

입력

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

출력

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

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

첫번째 풀이

num = []
for i in range(int(input())):
    num.append(int(input()))
    
#sort함수로 정렬
num.sort()

#for문만 사용해서 오름정렬
#for i in range(len(num)):
#     for j in range(i + 1, len(num)):
#         if num[i] > num[j]:
#             num[i], num[j] = num[j], num[i]
for j in num:
    print(j)

평소 풀던데로 풀었더니 메모리초과, 시간초과로인해 실패했다.

최소한의 메모리와 최소한의 시간을 사용하는 방법을 생각해봐야겠다.

두번째 풀이

import sys

num = [0] * 100001  # 10,000보다 작거나 같은 자연수리스트를 만들어준다.

for i in range(int(sys.stdin.readline())):
    num[int(sys.stdin.readline())] += 1  # 입력값의 인덱스에 1씩 추가 해준다.

for j in range(10001):
    if num[j] != 0:  # 해당 인덱스의 값이 0 이 아니라면 해당 인덱스를 인덱스의 값만큼 출력해준다.
        for k in range(num[j]):
            print(j)

for문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져서 반복을 할 때마다 메모리 초과가 발생한다.

그래서 시간도 초과하고 메모리도 초과했던 것 같다.

느낀 점

무작정 코드부터 작성하지 않고, 문제의 조건부터 꼼꼼히 확인해 조건을 지키면서 문제를 풀어야겠다.