020 수 정렬하기 2

첫번째 코드

 

병합정렬을 이용하여 2개로 나눈 후 병합정렬을 진행하자는 아이디어로 출발했다!

 

import sys
input = sys.stdin.readline

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

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

divide_point = n // 2

data1 = a[:divide_point]
data2 = a[divide_point:]

index1 = 0
index2 = 0
i = 0

answer = [0] * n

# 나누어진 데이터 내 정렬
data1.sort()
data2.sort()

# 병합된 데이터끼리 병합정렬 진행
while data1 and data2:
    if data1[0] < data2[0]:
        answer[i] = data1.pop(0)
    else:
        answer[i] = data2.pop(0)
    i += 1

while data1:
    answer[i] = data1.pop(0)
    i += 1

while data2:
    answer[i] = data2.pop(0)
    i += 1

for i in answer:
    print(i)

 

결과는 맞는 듯 하지만 시간초과가 나온다...

---

두번째 코드

 

책을 참고하여 첫번째 코드에서 집합을 분할하는 과정도 일반화하여 들어갔다.

 

import sys
input = sys.stdin.readline

def merge_sort(s, e):
    if e - s < 1:
        return
    m = int(s + (e - s) / 2)
    merge_sort(s, m)
    merge_sort(m + 1, e)
    
    
    for i in range(s, e + 1):
        tmp[i] = a[i]
    
    k = s
    index1 = s
    index2 = m + 1

    while index1 <= m and index2 <= e:
        if tmp[index1] > tmp[index2]:
            a[k] = tmp[index2]
            k += 1
            index2 += 1
        else:
            a[k] = tmp[index1]
            k += 1
            index1 += 1

    while index1 <= m:
        a[k] = tmp[index1]
        k += 1
        index1 += 1
    while index2 <= e:
        a[k] = tmp[index2]
        k += 1
        index2 += 1
    
n = int(input())
a = [0] * int(n + 1)
tmp = [0] * int(n + 1)

for i in range(1, n+1):
    a[i] = int(input())

merge_sort(1, n)

for i in range(1, n+1):
    print(str(a[i]))

 

통과!

 

근데 두 개의 계산 차이가 그렇게 많이 나는지는 아직 잘 이해가 어렵다...

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/2751.%E2%80%85%EC%88%98%E2%80%85%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0%E2%80%852

programmers/백준/Silver/2751. 수 정렬하기 2 at main · ornni/programmers