BAEKJOON #10989 수 정렬하기 3

이 문제의 저작권은 BAEKJOON에 있습니다.

 

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

문제는 위 링크에서 확인할 수 있습니다.

import sys
N = int(input())
arr = [0] * 10001
for i in range(N):
    a = int(sys.stdin.readline())
    arr[a] = arr[a] + 1
arr_size = len(arr)
for b in range(arr_size):
    if arr[b] !=0:
        for c in range(arr[b]):
            print(b)

단순한 정렬 방법으로는 통과할 수 없는 문제였습니다.

시간과 메모리 모두 생각해야하는 문제여서 풀이 방법을 찾기 어려웠습니다.

 

해결 방법은 생각보다 간단합니다.

문제에서 제한하는 범위의 배열을 미리 만들어둡니다.

 

input으로 숫자가 입력되면 미리 만들어둔 배열의 해당 숫자의 index의 요소 값을 증가시킵니다.

모든 값을 입력받았다면 0을 제외하고 index의 요소만큼 index를 출력합니다.

예를 들어 [0],[2],[1],[0],[0]....... 인 배열이라고 할 때 출력은 1, 1, 2입니다.