[정렬] 백준 #10989 수 정렬하기 3 - Python

📚 문제

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

10989번: 수 정렬하기 3

 

💡 접근법

계수 정렬 알고리즘을 이용하여 구현하였다.

계수 정렬이란?
각 원소들 간의 비교 없이, 크기를 기준으로 개수를 세어 정렬하는 방법이다.

 

💻 코드

1) 전체 코드

import sys

N = int(sys.stdin.readline())
count = [0] * 10001

for _ in range(N):
    count[int(sys.stdin.readline())] += 1

for i, c in enumerate(count):
    for _ in range(c):
        print(i)

 

2) 해설

(1) 패키지 Import

import sys

파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리를 사용하였다.

 

(2) 입력받기

N = int(sys.stdin.readline())

수의 개수(N)을 입력받고 int로 형변환하였다.

 

(3) 계수 정렬 구현

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

입력받은 리스트 내에 속해있는 모든 원소를 인덱스로 가지는 count 리스트를 생성한다.

이때 입력으로 들어올 수 있는 최댓값 + 1을 리스트의 크기로 지정하고 0으로 초기화한다.

 

값을 입력받음과 동시에 count 리스트에서 입력받은 값을 인덱스로 갖는 요소의 값을 1 증가시킨다.

 

(4) 출력하기

for i, c in enumerate(count):
    for _ in range(c):
        print(i)

count 리스트를 순차적으로 순회하면서 접근한 요소의 값만큼 해당 인덱스를 출력한다.

 

✅ 정답 확인

 

---

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!

읽어주셔서 감사합니다^.^