[Do-it! 코딩 테스트-기초편] 022. 수 정렬하기 3

문제

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

10989번: 수 정렬하기 3

---

접근

데이터 크기: 10,000,000

시간 제한: 5초

메모리 제한: 8MB

 

데이터 크기가 크고 시간에 제약이 없다면 카운팅 정렬을 사용하는 것이 좋다.

---

코드

import sys

N = int(sys.stdin.readline())
array = [0] * 10001
for i in range(N):
    a = int(sys.stdin.readline())
    array[a] += 1

for i in range(10001):
    if array[i] != 0:
        for j in range(array[i]):
            print(i)

---

설명

입력받는 모든 값에 해당하는 인덱스를 가지는 리스트를 만든다.

여기서는 크기가 10001인 인덱스를 만들었고

입력받은 리스트값에 해당하는 인덱스의 값을 1 올린다.

중복이 있다면 그 값은 중복한 횟수만큼 증가한다.

 

완성된 리스트는 0번 부터 끝까지 순으로 0이 아닌 수가 있다면 출력한다.

만약 중복이 있어서 리스트에 2 이상의 값이 존재한다면 개수만큼 출력한다.