[Python]백준 BaekJoon.AC 10989 : 수 정렬하기3(sys, list)

 

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

10989번: 수 정렬하기 3

 

 

입력 최대 개수는 10,000,000개지만 입력값의 최대값은 10,000이다.

양은 많지만 그 가짓수는 비교적 적다는 조건을 이용했다.

그래서 리스트를 애초에 10,001개 만들어줬고(0~10,000)

입력값에 따라 1씩 카운트를 증가해줬다.

 

이렇게 되면 굳이 입력값이 무엇인지 저장하지 않아도 되고(리스트의 입력값번째에 카운트해주니까)

값에 따라 카운트만 해주면 되니 간편하다.

 

출력은 0부터 10,000까지의 리스트를 훑으며 진행되고, 만약 0이 아닌 값을 가지고 있다면 (그 값은 i의 입력 횟수일테니)

i를 값만큼 반복해 출력한다. 0을 가지고 있다면 i는 한번도 입력받지 않음을 의미한다.

 

 

모든 경우의 수를 애초에 준비했기 때문에(입력 가능한 1~10,000번째 리스트)

굳이 오름차순으로 정렬할 필요는 없었다. 어차피 1부터 훑을테니까.

 

이는 다르게 생각하면 출제자가 의도한 정확한 풀이는 아니라는 뜻일 것이다.

그래서 딕셔너리를 이용해봤는데 오히려 시간이 더 길게 나와서...;;

(입력값이 존재하지 않으면 1과 함께 등록해주고, 존재하면 카운트를 올려주는 방식이었다)

 

리스트 풀이법도 마냥 짧은 소요시간은 아니었지만 이렇다할 멋진 방법은 없는 것 같아 이만 넘기기로 했다.

 

 

 

import sys

N = int(input())
num = [0 for i in range(10001)]

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


for i in range(10001):
    if num[i] != 0:
        for k in range(num[i]):
            print(i)