[Algorithm] [Python] 백준/BOJ - 10989 _ 수 정렬하기 3

10989 - 수 정렬하기 3

문제

---

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

---

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

---

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

제출 코드

---

1차 제출 코드

from sys import stdin

''' N 개의 수가 주어졌을떄 이를 오름차순 정렬하라 '''

def QuickSort(arr):
    if len(arr) <= 1:
        return arr
    lesser_list, equal_list, greater_list = [], [], []
    pivot = arr[len(arr) // 2]
    for item in arr:
        if item < pivot:
            lesser_list.append(item)
        elif item > pivot:
            greater_list.append(item)
        else:
            equal_list.append(item)

    return QuickSort(lesser_list) + equal_list + QuickSort(greater_list)

def main():
    series = [0] * 10001
    n = int(stdin.readline())
    tmp = [int(stdin.readline()) for _ in range(n)]
    arr = QuickSort(tmp)
    for item in arr:
        print(item)

if __name__ == "__main__":
    main()

본 문제는 시간 제한과 메모리 제한이 걸려있다.

이를 참고하여 일단은 입력 배열이 차지하는 메모리만을 사용하여 in-place Sorting 방식으로 QuickSort 를 구현하였다. 하지만 가차없이 메모리 초과가 떳다..ㅎㅎ

이러한 문제를 처음 접해봐서 많은 삽질을 했다.

삽질의 결론은 메모리 제한으로 인해 모든 입력값을 순수히 입력받고 정렬하는 방법으로는 문제를 해결할 수 없다.

문제를 풀기 위한 핵심 key는 아래와 같다.

• 값을 입력받지 않고 값을 저장하는 방법을 생각해내야 한다.

• 숫자의 위치와 인덱스 값을 매핑해주면 정수를 저장할 필요 없이 인덱스를 통해 접근이 가능하다.

• 입력받을 수의 범위는 10,000보다 작거나 같은 자연수다.

위 내용을 상기하고 제출한 코드는 아래와 같다.

최종 제출 코드

from sys import stdin

sr = lambda : stdin.readline()
n = int(sr())

arr = [0 for _ in range(10000)]

for _ in range(n):
    arr[int(sr()) - 1] += 1

for i in range(len(arr)):
    if arr[i] != 0:
        for j in range(arr[i]):
            print(i+1)

문제 풀이

---

위 문제는 메모리 사용에 제한이 있는 문제다.

따라서, 입력받은 내용을 어디에 저장한 이후에 정렬을 진행하기에는 다소 무리가 있다.

입력값의 범위는 10,000보다 작거나 같은 자연수이므로 길이 10,000의 배열을 앞서 선언한다.

이후 입력받은 정수값에 대응되는 인덱스 위치에 값을 1 올린다. 이를 통해 정수 몇을 입력받았는지, 중복되는 숫자를 받을 경우 몇번 중복되었는지 확인이 가능하다.

이후 배열을 순회하며 원소 값이 0이 아닌 경우에 한해 출력을 진행한다.

출력을 진행할때는 중복 입력받은 값에 대한 경우를 고려하여 이중 포문을 통해 값을 출력한다.

다른 사람의 풀이

---

import sys
input = sys.stdin.readline
num_list = [0 for x in range(10001)]
case = int(input())
for x in range(case):
    num_list[int(input())] += 1
for x in range(10001):
    print('%s\n'%x*num_list[x],end='')

문제를 푸는 흐름은 필자와 동일하지만 출력 로직에 차이가 있다.

필자는 원소값이 0인지 if 문을 통해 필터링을 진행하고 출력을 진행했으나 위 코드는 * 연산을 통해 0을 곱하면 0이되어 출력을 안하는 방법을 활용하셨다.