[백준/10989] 수 정렬하기 3 (with 파이썬)

✔ 문제

---

✔ 풀이

🍣 틀린 코드 (메모리 초과)

import sys
input = sys.stdin.readline

n = int(input())
nums = []

for _ in range(n):
    nums.append(int(input()))

max_num = max(nums)
count = [0] * (max_num + 1)
sorted_nums = []

for i in nums:
    count[i] += 1

for i in range(max_num + 1):
    for _ in range(count[i]):
        sorted_nums.append(i)

for i in sorted_nums:
    print(i)

계수 정렬을 사용하라길래 사용해봤더니 메모리 초과가 떴다 (〃⌒▽⌒〃)ゝ

 

 

🍔 정답 코드

import sys
input = sys.stdin.readline

n = int(input())
nums = [0] * 10001

for _ in range(n):
    x = int(input())
    nums[x] += 1

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

---

✔ 설명

🥐 틀린 코드와 정답 코드의 차이점

1. nums에 입력 받은 숫자만 append하는 것이 아니라 입력으로 들어올 수 있는 수의 범위 만큼 배열 길이를 미리 지정해놓는다.

2. 최댓값, 계수를 카운트 하는 배열, 카운트한 계수의 수를 저장하는 배열 등 여러 변수를 계속 초기화하지 않는다. (메모리 부족함)

3. 입력받을 수 있는 수 만큼 할당된 nums에 바로바로 새로운 수를 입력받으면서 입력받은 인덱스의 값을 +1 해준다.

    ㄴ ex) 4 입력 시 nums[4] += 1

4. nums의 길이만큼 for문을 돌아 만약 nums[i]가 0이 아니라면 nums[i]의 값만큼 해당 값을 출력하면 된다.

---

✔ 후기

계수 정렬 진짜 이번에 백준 알고리즘으로 처음 접해본 것 같다.

어떤 정렬인지 몰라서 알고리즘부터 공부하고 해당 알고리즘으로 바로 풀어봤는데 역시나 메모리 초과가 떴다.

아무래도 여러 변수를 초기화하여 할당받은 부분과 처음 nums를 입력받을 수 있는 범위만큼의 길이로 할당해놓지 않은 것이 패착이었던 것이라 생각된다.