[알고리즘] 백준 10989 (파이썬 풀이)

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

10989번: 수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

해결코드

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

for i in range(n):
      cnt = int(sys.stdin.readline())
      li[cnt] += 1
for i in range(10001):
  if(li[i] != 0):
    for j in range(li[i]):
      print(i)

문제풀이

일단 이 문제는 수 정렬하기 세번째 문제이다. 차이점은 시간제한과 메모리제한에 차이를 뒀다는 점인데

수정렬하기1,2번과 같이 풀면 시간초과로 문제를 해결하지 못한다.

그래서 일단 수가 10000보다 작거나 같은 수로 나왔으니 10000개의 리스트를 만들어서

입력받은값을 리스트에 일치하는 인덱스 값에 넣어놓고 나중에 그 수만큼

인덱스를 출력하는 원리로 문제를 풀었다.

코드를 보면

일단 입력시간을 줄이기위해 readline을 사용하여 n을 받았다.

수가 1부터 시작하므로 10001개의 리스트를 만들어주고 일단 모든 원소를 0으로 초기화해준다.

n만큼 for문을 돌리는데

cnt값에 입력값을 저장한다.

그리고 리스트의 li[cnt] 인덱스에 +1을 한다.

for문을 나오고 다시 10001범위의 for문을 돌린다.

li값이 0이 아니라면 그 리스트 인덱스 값을 개수만큼 출력해준다.