[Algorithm] 백준 10989번 수 정렬하기 3

 

정렬 문제인데, 메모리 제한이 있어서 시간이 꽤 걸린 문제였다.

무려 '네 번째 시도'만에 성공한 문제. (정답은 아래 '네 번째 시도'에 있습니다.)

 

 

 📌 첫 번째 시도

처음에는 아래와 같이 리스트에 입력값을 모두 담아서 sort를 하려고 했으니 메모리 초과가 나타났다.

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

for _ in range(n):
    a = int(input())
    x.append(a)
    
x.sort()

for j in x:
    print(j)

 

 

 📌 두 번째 시도

조금 더 속도가 빠른 정렬을 찾아보다가 퀵정렬을 사용해봐도 되겠다라는 생각이 들어서, 함수를 구현하고 적용을 시켜보았다.

그러나 역시나 메모리 초과.

# 퀵 정렬 함수
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = len(arr)//2  # pivot을 인덱스로 지정
    front_arr, pivot_arr, back_arr = [], [], []  # 빈 리스트 초기화

    # arr에 있는 숫자를 하나씩 꺼내가면서 
    for val in arr:
        if val < arr[pivot]:
            front_arr.append(val)
        elif val > arr[pivot]:
            back_arr.append(val)
        else:
            pivot_arr.append(val)

    return quick_sort(front_arr) + quick_sort(pivot_arr) + quick_sort(back_arr)


# 빈 리스트에 입력값 넣기
x = []     # 값을 넣을 빈리스트
n = int(input())   # 값의 개수 

for i in range(n):
    a = int(input())
    x.append(a)

# 퀵 정렬 함수 적용
sorted_x = quick_sort(x)

# 정렬 결과 출력
print("정렬된 리스트:", sorted_x)

 

 

 📌 세 번째 시도

혹시 입력 값을 한번에 받고 진행하는게 속도와 메모리에 영향을 끼칠까 하여, 입력 값을 받는 즉시 sort를 진행하는 방법도 구현해보았다.

-> 메모리 초과........(이런...........)

# 값을 모두 받은 후 하는 것이 아니라, 받으면서 sort할 수 있는 방법이 있을까?

x = []     # 값을 넣을 빈리스트
n = int(input())   # 값의 개수 

for i in range(n):
    a = int(input())
    # 첫번째 값은 그냥 넣기
    if i == 0:
        x.append(a)
    # x리스트의 이전 값과 현재 값 비교해서 sort
    x.append(a)  # 우선 x에 값 넣기
    if x[i-1] > x[i]:
        x[i-1], x[i] = x[i], x[i-1]  # sort
    elif x[i-1] <= x[i]:
        pass


for j in x:
    print(j)

 

 

 📌 네 번째 시도

더 찾아보던 중, '계수 정렬'을 발견하였다. 빈 리스트를 숫자의 최댓값으로 만들어둔 뒤에 해당 숫자가 나올때까지 count하는 방법이다. 처음 알게 된 방법이라서 새롭고 흥미로웠다. 

그리고 입력을 for문을 통해서 여러개 받는 경우, 메모리 초과 문제가 발생할 수 있다고 하여, sys의 sys.stdin.readline()을 이용하여 입력을 받았다. 

이때, n을 입력 받는 부분은 for문이 아니기도 하고 첫 input이라서 상관없다고 한다. 그래서 for문 안의 입력 값을 받는 부분만 sys.stdin.readline()을 적용해주었다. 

-> 드디어..... 메모리 통과ㅜㅜ

# 계수 정렬 활용

import sys
# input = sys.stdin.read

n = int(input())   # 값의 개수 

# 메모리 사용을 최소화하기 위해 10000개의 0으로 이루어진 리스트 초기화
cnt = [0] * (10000 + 1) # 입력값이 10000개까지 주어지니 10000 + 1개의 리스트 선언

for _ in range(n):
    a = int(sys.stdin.readline())
    cnt[a] += 1  # for문을 돌며 각 데이터에 해당하는 인덱스 값을 +1 한다. 

for i in range(len(cnt)):
    for _ in range(cnt[i]):  # cnt의 인덱스 하나를 돈다.
        print(i)   # i를 cnt의 값만큼 출력하고 빠져나와 그 다음 i+1번째 인덱스로 이동한다.