백준 10989 - 수 정렬하기 3

생각의 틀을 전환해야 풀 수 있는 문제다.

문제에 힌트가 있는데, 수 정렬하기 시리즈 1,2번 문제는
"어떻게 더 효과적인 정렬 알고리즘을 쓸 것인가?" 에 대한 질문이었다면, 이번 문제는
"이런 방법으로도 생각할 수 있다" 라는 느낌이었다.

우선 python연습을 위해 python으로 시도하였는데, 2번 문제의 코드와 똑같이 제출해 봤다.

import sys
n = int(input())
l = []
for i in range(n):
    l.append(int(sys.stdin.readline()))
for i in sorted(l):
    sys.stdout.write(str(i)+'\n')

stdin,stdout으로 최대한 메모리 사용을 줄이려고 했으나, 결과는 실패. 사실 이 문제는 어떤 정렬 알고리즘을 쓰더라도 시간 초과가 나오도록 설계되어있다. 그 이유는 N의 개수가 10,000,000개이기 때문이다.

따라서 다른 접근을 해야 하는데, 다행히 주어지는 수들은 10,000보다 작거나 같은 자연수이다.

해답은 간단하다. 그러나 생각하기가 쉽지 않았다.
먼저, 가능한 범위 내의 자연수를 마킹할 수 있는 배열을 선언한다.
그 후 수를 하나씩 읽을 때마다 해당 인덱스에 카운팅을 한다.
결과적으로 10,000보다 작은 자연수들이 각각 몇 개 있는지 카운팅이 되어있는 배열이 완성되고, 그 배열의 인덱스의 개수만큼 해당 인덱스를 출력하면 성공!

import sys
n = int(sys.stdin.readline())
l = [0]*10001

for i in range(n):
    l[int(sys.stdin.readline())] +=1

for i in range(10001):
    if l[i] != 0:
        for answer in range(0,l[i]):
            sys.stdout.write(str(i)+'\n')

발상의 전환을 요구하는 문제라 신선했다.