백준 알고리즘 | 10989 : 수 정렬하기 3 (Python / 파이썬)

---

수 정렬하기 3 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초 (하단 참고)	8 MB (하단 참고)	79728	17455	13045	22.841%

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

10989번: 수 정렬하기 3

---

문제

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

​

입력

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

​

출력

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

​

알고리즘 분류

정렬

---

백준 알고리즘 # 10989번 : 수 정렬하기 3

import sys
n = int(input())
check_ls = [0] * 10001

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

for i in range(10001):
    if check_ls[i] != 0:
        for _ in range(check_ls[i]):
            print(i)

풀이

이 문제도 저번에 풀었던 수 정렬하기 2와 비슷하게 "메모리 초과"가 문제였어요.

(백준 알고리즘은 시간 초과, 메모리 초과의 변수가 상당하네요😂)

​

IDE상에서는 input()함수와 sorted로 정렬해서 출력하는 것도 괜찮았지만

key point 1

이번 문제에서는 메모리 제한이 8MB라는 점과 N의 수가 10,000보다 작거나 같은 자연수로 주어져서

이것에 대한 제한을 걸고 풀어야 한다는 것을 문제를 읽고 알았어야 해요!

check_ls 변수로 체크할 리스트를 설정했어요.

​

key point 2

그 다음으로 좀 더 빠른 입력을 위해

import sys

sys.sydin.readline()

위 방식으로 수를 입력받은 뒤

​

for문으로 입력받은 n의 수만큼 반복을 해주면서

num 변수로 그 다음 정수들을 입력받고

check_ls[num]로 새로이 초기화 시켜줬어요! (0에서 1로 바꿔줌)

​

그리고 for문으로 다시 10001이라는 범위 안에서 i를 반복해주고

만약 check_ls[i]가 0이 아닐 경우, 즉 1 이상의 수로 초기화 시켜준 애들인 경우​​에만

for문으로 check_ls[i]에 입력된 수 만큼 그 수를 출력시켜주면 풀이 끄-읏👏

​

key point 3

이것에 대해서 예를 살짝 들자면, 5가 2번 입력되면 첫 번째 for문이 돌아갈 때

check_ls[5]는 1이 아니라 2번 입력되었으니 +1이 한번 더해져서 2가되요.

그럼 마지막 출력에 있는 for문에서 range(2)로 설정되어서 0, 1 두 번 돌아가니

print(i)로는 2번 출력되어서 10001번 안에 5라는 숫자가 돌아갈 때 2번 찍히는 것이죠!

​

자세한 코드가 궁금하신 분들은 아래 GitHub 코드를 참고해주세요🙏

wook2124/Algorithm-Test

최종 소스코드