[정렬] boj 10989. 수 정렬하기3

첫 번째 풀이 : sort() 사용 -> 메모리 초과

풀릴 리 없는 줄은 알았지만, 그래도 바로 떠오르는 방법을 해 봐야 직성이 풀리는 스타일인지라 한번 해 봤습니다.

import sys
input = sys.stdin.readline

t = int(input())
ans = []

for i in range(t):
    ans.append(int(input()))
ans.sort(key=lambda x : x)
for i in ans:
    print(i)

두 번째 풀이 : counting sort -> 메모리 초과

파이썬에서 사용하는 sort() 와 sorted() 메소드는 팀 정렬이라는 방식을 사용한다고 합니다. 이와 유사히 볼 수 있는 방식이 퀵 정렬이고, 정렬을 사용할 때 가장 일반적으로 많이 사용하는 방식입니다. 퀵 정렬의 시간복잡도(참고링크첨부)는 O(N*logN)입니다.

이 문제에서는 N의 범위가 상대적으로 큰 편인데, 그에 비해 제시될 숫자의 범위가 작으므로 시간복잡도 측면에서 퀵 정렬보단 계수 정렬(counting sort)이 더 적합합니다. 계수 정렬은 시간복잡도가 O(N*K)입니다. 여기서 K는 제시될 수 있는 숫자의 범위인데, 해당 문제에서는 10,000 이하의 자연수라고 제시되었으므로 계수 정렬이 더 유리한 것입니다.

단, 정답을 알고 난 뒤 더 주의했어야 했구나 하는 점은, 이 문제의 관건은 공간복잡도였으므로 계수 정렬 알고리즘을 사용하더라도 배열 등의 사용에 좀 더 신중했어야 했습니다.

import sys
input = sys.stdin.readline

# counting sort : 숫자의 범위가 작고, 개수가 적을 때 효과적인 정렬 방법
def counting_sort(arr):
    counting_sum = [0]*(max(arr)+1)

    # 개수 세기
    for i in arr:
        counting_sum[i] += 1

    # 누적합 구하기
    for i in range(1,len(counting_sum)):
        counting_sum[i] += counting_sum[i-1]

    # 결과 배열 생성
    res = [0]*len(arr)

    for i in arr[::-1]:
        res[counting_sum[i]-1] = i
        counting_sum[i] -= 1
    return res

t = int(input())
arr = []
for i in range(t):
    arr.append(int(input()))
for i in counting_sort(arr):
    print(i)

세 번째 시도 코드 -> 통과

계수 정렬도 처음이었는데, 공간복잡도에 대한 이해도도 낮아서 쉽게 접근하기에 어려움을 겪었습니다... 고민하다가 결국 구글링의 도움을 받게 되었습니다...

더 열심히 공부하자...!

import sys
input = sys.stdin.readline

t = int(input())
arr = [0] * 10001

for _ in range(t):
    arr[int(input())] += 1

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

놀라운 점은, 아래 코드를 pypy로 제출하면 메모리 초과가 나옵니다. 이는 pypy와 python3 중에서 메모리를 더 많이 사용하는 것은 상대적으로 pypy라는 것 같은데, 해당 내용에 대해서는 한번 알아봐야겠습니다.

-- chatGPT 답변:

Pypy와 Python3는 각각 다른 구현 방식을 가진 파이썬 인터프리터입니다. Pypy는 Just-In-Time 컴파일러를 사용하여 실행 속도를 높이는 데 초점을 맞추고 있습니다. 일반적으로 Pypy는 Python3보다 실행 속도가 빠르지만, 경우에 따라 메모리 사용량이 더 클 수 있습니다.

메모리 사용량은 코드와 알고리즘에 따라 다르게 나타납니다. 따라서 Pypy가 항상 Python3보다 메모리 사용량이 크다고 단정할 수는 없습니다. 특정 문제나 상황에서 Pypy가 더 많은 메모리를 사용할 수도 있고, 그렇지 않을 수도 있습니다.

결론적으로, Pypy와 Python3의 메모리 사용량은 상황에 따라 다르게 나타납니다. 둘 중 어떤 것이 더 적은 메모리를 사용하는지는 실행하는 코드와 알고리즘에 따라 달라집니다. 때로는 Pypy가 더 많은 메모리를 사용할 수 있지만, 그렇지 않은 경우도 있습니다.