[백준-10989] 수 정렬하기3 파이썬, 계수정렬

# 문제

# 풀이

쉽다고 생각 할 수 있는데, 주어진 메모리가 너무 작다. 그렇기 때문에 시간을 손해보더라도 메모리를 적게쓰는 방법을 사용해서 문제를 풀어야한다. 천만개의 입력이 들어올 수 있고, 입력받은 정수를 모두 저장하는 배열을 사용하면 무조건 메모리초과가 뜬다.

## 실패했지만 잘 접근했던 풀이

import sys

def not_solve():
  N = int(input())
  data = dict()
  arr = []
  for _ in range(N):
    num = int(input())
    if num not in data:
      data[num] = 1
      arr.append(num)
    else :
      data[num] += 1

  arr.sort()

  for i in arr:
    for _ in range(data[i]):
      print(i)

간단하다. 딕셔너리를 사용해서 만약에 딕셔너리에 값이 들어온 적이 없다면 해당 딕셔너리 관계를 만들어주고 초기화(1)로 설정해준다. 다음에 딕셔너리에 있는 값이 들어오면 +1을 해준다. 그리고 들어온 값들에 최초 한번 리스트에 저장해서 해당 리스트를 정렬해주고, 딕셔너리에 맵핑되어있는 count된 값들만큼 출력해서 정렬을 수행했다. 아쉽게도 시간초과가 떴다. 데이터를 순회하고, sort하면서 너무 많은 자원을 낭비 한게 아닐까 싶다.

## 계수정렬을 이용한 풀이

def solve():
  N = int(input())
  arr = [0] * 10_001
  for _ in range(N):
    num = int(sys.stdin.readline())
    arr[num] += 1

  for i in range(10_001):
    if arr[i] == 0:
      continue
    for j in range(arr[i]):
      print(i)


if __name__ == '__main__':
    solve()

위 풀이와 접근법은 유사하지만, 딕셔너리의 키를 탐색하는 시간과, 들어왔던 값들을 sort하는데 드는 시간을 아낄 수 있다. 최초로 가능한 수만큼을 미리 배열에 만들어 놓고, 해당 인덱스가 그 수의 key이고 인덱스에 저장되는 값이 호출된 개수이다. 해당 개수를 하나씩 늘려가는 방법을 사용하면 된다. 위 방법을 계수정렬이라고 한다 했다.

# 마치며

하지말라는거 한번씩 다 떠봤다ㅋㅋㅋ