🔗 알고리즘 분류 정렬
문제 출처 https://www.acmicpc.net/problem/10989
이 문제와 똑같은 문제를 풀었던 기억이 난다. 백준 2751번 정렬 문제인데(백준 2751번), 똑같은 정렬 문제라고해서 똑같이 풀었다가는 메모리 초과 파티를 맞이할 수 있다.
시간복잡도만을 평소에 고려하며 풀었던 터라 메모리 초과 폭탄을 맞이하고 꽤나 당황스러웠다. 이 문제를 풀 때 핵심은 두 가지이다.
1. input 대신 sys.stdin.readline을 사용하는 것
2. 정렬하는 방법으로 sort() 함수를 사용하지 말 것
우선 코드를 살펴보도록 하자
📌 코드
Python
import sys
input = sys.stdin.readline
arr = [0] * 10001
n = int(input())
for _ in range(n):
number = int(input())
arr[number] += 1
for k in range(10001):
if arr[k] != 0:
for i in range(arr[k]):
print(k)📌 풀이
우선 오름차순을 할 숫자들을 받아야하는데 그 수들의 범위와 크기를 고려했을 때 단순히 input()으로 입력받게 되면 메모리 초과가 발생한다. input()대신 sys.stdin.readline()으로 수들을 입력받도록 한다.
또한 메모리 제한이 적기 때문에 위에서 언급한 것처럼 sort 내장함수를 사용할 수 없다. 따라서 정렬 로직을 배열로 해결한다. 입력되는 수는 10000 이하의 수이다. 입력되는 수가 배열의 인덱스와 일치하도록 하기 위해 크기가 10001인 배열을 모두 [0]으로 초기화한다.
이제 차례로 입력을 받는 것인데, 만약 5가 input으로 들어왔으면 배열[5]의 값을 하나 늘린다.(arr[5]+=1)
입력이 끝난다면 배열의 각 요소에는 인덱스에 해당하는 수가 입력된 횟수대로 저장이 되어있을 것이다. 예를 들면 5가 3번 입력이 되었다면 arr[5]에는 3이 저장되어 있을 것이다.
for문을 통해 배열을 인덱스 0부터 10000까지 돌리며 해당 요소에 들어있는 값만큼 인덱스에 해당하는 숫자를 반복하여 출력한다.
