[BOJ] Python 백준 10989번 수 정렬하기 3 실버 5

해당 문제와 비슷하지만 조건에서 차이가 나기 때문에 정렬 함수를 이용해서 푼 문제가 있다.

 

정렬 함수가 다소 익숙하지 않다면 해당 포스팅을 참고해서 익숙해지면 좋을 것 같다.

 

https://khsung0.tistory.com/37

[BOJ] Python 백준 2751번 수 정렬하기 2 실버 5

문제 풀이

---

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

10989번: 수 정렬하기 3

 

이번 문제도 데이터를 입력받아 정렬한 뒤 오름차순으로 출력하는 부분은 동일하지만 윗 문제와 다르게 수의 범위가 10000 이하인 자연수이다.

 

이 조건이 중요한 이유는 수의 범위가 충분히 적기 때문에 각 인덱스를 해당 숫자로 생각하여 카운팅으로 정렬할 수 있기 때문이다.

 

이 정렬 방식은 계수 정렬(Counting Sort)이라 하며 계수 정렬 자체는 다소 사용하는 경우가 적을지라도 해당 방법이 인덱스를 원소로 여기는 방식이기 때문에 학습하면 좋다.

 

인덱스를 원소로 여기는 방식은 Union-Find 알고리즘 같은 부분에서 집합들의 부분 집합을 구한다든가 최소 신장 트리(Minimum Spanning Tree)에서 사이클을 찾는데 자주 쓰이기 때문이다.

 

관련 알고리즘들을 포함하여 알아야 될 법한 알고리즘들은 직접 작성한 "쉽게 풀어쓴 자료구조와 알고리즘" 전자책에 자세하고 쉽게 설명해 놓았으니 관심 있는 사람은 한 번씩 구경하면 좋을 것 같다.

 

다시 문제로 넘어와서 실버 5 치고는 상당히 낮은 23%의 정답 비율이 나타나는데 어려운 개념이 필요한 문제가 아니므로 전체 코드를 보면 쉽게 이해할 수 있을 것이다.

 

import sys
n=int(input())
num_list=[0 for i in range(10000)]
for i in range(n):
    num_list[int(sys.stdin.readline())-1]+=1
for i in range(len(num_list)):
    for j in range(num_list[i]):
        print(i+1)

 

num_list는 9999까지(파이썬의 for문은 10000 미만까지 반복하기 때문에) 0으로 초기화했는데 이 부분은 수의 범위가 10000 이하인 자연수이기 때문에 0번째 인덱스는 1을, 1번째 인덱스는 2를 의미한다.

 

만약 인덱스와 숫자가 헷갈린다면 10000까지(range(10001)) 초기화시키고 1번째 인덱스를 1로 생각하면 된다.

 

또한 입력받을 때 sys 모듈을 import 하여 sys.stdin.readline()을 사용하였다.

 

내장 함수인 input()은 prompt message를 출력하고 각 줄의 개행 문자를 삭제하지만 sys.stdin.readline()은 이러한 작업 없이 각 줄을 입력받기 때문에 입력 양이 많을수록 input() 보다 sys.stdin.readline()이 더 효율적이다.

 

이 차이로 인해 통과와 시간 초과가 갈리는 경우가 많으니 많은 양을 입력받는 문제에서 활용하는 것이 좋다.

 

5번째 줄에서 해당 원소가 뜻하는 인덱스의 값을 카운팅 해주면 해당 원소는 그만큼 입력받았단 뜻이다.

 

즉 0번째 인덱스의 값이 1이라면 1을 한 번 입력받은 거고 3번째 인덱스의 값이 2라면 4를 두 번 입력받은 것이다.

 

따라서 6번째 줄에서 num_list를 전체 반복하며 num_list [i]가 1 이상이라면 해당 횟수만큼 반복하여 원소를 출력하면 된다.

 

결과 화면

 

조건에 따라 유연하게 방식을 적용하는 게 중요한 문제인 것 같다.