문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
내 풀이
import sys
input = sys.stdin.readline
n = int(input())
list1 = []
for _ in range(n):
list1.append(int(input()))
list1.sort()
for x in list1:
print(x)N이 10,000,000까지라서 불안하긴 했지만 브론즈니까...했는데 역시나 메모리 초과로 실패가 떴다.
아래는 알고리즘을 사용해서 효율적으로 해결해서 정답을 받은 코드 (설명은 코멘트에서)
import sys
input = sys.stdin.readline
n = int(input())
cnt = [0]*(10000+1)
for _ in range(n):
cnt[int(input())] += 1
for i in range(len(cnt)):
if cnt[i]!=0:
for _ in range(cnt[i]):
print(i)코멘트
이 문제는 계수 정렬이라는 알고리즘을 사용해서 풀어야 하는 문제이다. 정렬해야 할 수가 많아지면 파이썬에서는 시간 초과나 메모리 초과가 뜨기 십상인데, 계수 정렬을 이용하면 훨씬 시간 복잡도가 적게 문제를 해결할 수 있다.
계수 정렬이란, 미리 초기화된 배열을 선언해두고 그 수가 있는 갯수만큼 count 수를 늘린 다음 그 배열의 count 수만큼 순서대로 출력을 하는 방식이다. 예를 들어 list1 = [5, 4, 7, 8, 4, 3]라는 배열이 있다고 하면, 배열 내의 최대값이 8이므로 0이 아홉 개로 이루어진 cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0]를 미리 선언해두고, 배열 내의 숫자들에 대해 count를 세는 방식이다. list1의 요소 순서대로, cnt[5] = 1, cnt[4] = 1, cnt[7] = 1, cnt[8] = 1, cnt[4] = 2, cnt[3] = 1 이런식으로 카운트 되어서, cnt = [0, 0, 0, 1, 2, 1, 0, 1, 1] 가 되기 때문에 cnt의 요소를 0은 프린트하지 않고 2 이상의 숫자는 여러번 프린트되도록 하면, [3, 4, 4, 5, 7, 8]과 같이 정렬되는 것이다.
더 자세한 설명은 reference를 참고하자. 굉장히 잘 정리해놓은 포스팅이라서 이해하는데 도움이 많이 되었다.
References
https://www.acmicpc.net/problem/10989
https://kill-xxx.tistory.com/21
https://kill-xxx.tistory.com/entry/python-%EA%B3%84%EC%88%98%EC%A0%95%EB%A0%AC
