[BOJ 10989][백준 10989번] 수 정렬하기 3 (파이썬 풀이)

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

 

🤔 문제 설명 및 입출력

---

 

 

✍ 접근 방법

---

그냥 정렬 문제라고 .sort() 한번 쓰고 출력하면 되는 문제는 절대 아니다. 백준 문제는 항상 단순해보이는 문제가 꼬림한 부분을 감추고 있기 때문이다.

 

 

보면 N이 최대 10,000,000개 들어올 수 있다.  sort()를 이용하려면 일단 저 10,000,000개의 입력을 받을 리스트를 만들어야하는데, 그 리스트 만들다가 메모리가 터지는 꼴이 눈에 선하다.

 

그래서 여기서는 꼼수를 쓴다. 주어지는 N개의 숫자를 숫자 그대로 저장하는게 아니라, 이 숫자가 몇개가 들어왔는지 카운트만 하는 용도로만 사용하는 것이다.

 

이후, 그 카운터에 위치에 맞는 숫자를 카운터의 크기만큼 반복하면서 출력하는 것이다.

 

말로 하려니 더 어렵다. 바로 코드를 보자.

 

👨‍💻 소스 코드

---

• 파이썬

 

import sys
sys.stdin = open('10989_input.txt','r')
input = sys.stdin.readline # 속도향상을 위해서 사용

N = int(input())
zero_lst = [0 for i in range(10000+1)] # 입력되는 숫자의 최대값이 10000 이므로 0~10000를 표시할 수 있는 크기로 만든다.
for i in range(N):
    zero_lst[int(input())] += 1 # 입력된 숫자를 인덱스 삼아서 zero_lst의 요소를 1씩 증가시킨다

for idx in range(10000+1):
    for i in range(zero_lst[idx]):
        print(idx)

 

🔥 강평

---

구현 자체는 어렵지 않은데, 이런 생각을 깨치는 과정이 어려웠던, 콜럼버스의 달걀 문제였다.

이런 식으로 다량의 입력이 들어올때 입력 자체를 저장하는게 아니라, 카운터 형식으로 저장하는 접근법을 뭐라고 했던 거 같은데...기억이 잘 안난다.

 

여하튼, 풀이가 굉장히 인상깊었던만큼 블로그에 다시 한번 정리한다.

나중에 유사한 문제가 나왔을때 이 날의 기억을 떠올릴 수 있었으면 좋겠다