[백준 10989번] 수 정렬하기 3 (Python)

문제

출처- https://www.acmicpc.net/problem/10989

 

풀이

어떻게 풀어야할까 고민하던 중 힌트가 이미 나왔다.

카운팅 정렬을 이용하면 풀 수 있다는 것이다.

그래서 아래와 같이 풀었다.

 

import sys

# 입력받기
input = sys.stdin.readline
n = int(input())

input_array = list()
for _ in range(n):
    input_array.append(int(input()))

# 카운팅 배열 선언
counting_array = [0] * (max(input_array)+1)
for num in input_array:
    counting_array[num] += 1

# 카운팅 직전 개수 더하기
for i in range(1, len(counting_array)):
    counting_array[i] += counting_array[i-1]

output_array = [-1] * len(input_array)

# 카운팅 인덱스 검색 후 아웃풋 배열에 삽입
for num in input_array:
    index = counting_array[num] - 1
    output_array[index] = num
    counting_array[num] -= 1

print(*output_array, sep="\n")

 

이렇게 정석같이 푸니 아래와 같이 메모리초과가 나왔다. T_T

 

그래서 중간 절차를 생략하고 배열하나를 이용해서 풀어보았다.

 

import sys

# 입력받기
input = sys.stdin.readline
n = int(input())

array = [0] * 10000
for _ in range(n):
    # 입력값을 배열 인덱스로 설정. 개수 추가해주기
    array[int(input())] += 1

for i in range(len(array)):
    if array[i] != 0:
        # 해당숫자의 개수만큼 출력
        for _ in range(array[i]):
            print(i)

 

이렇게 바로 출력으로 이어지게 하니 맞았다!