[SW Expert Academy] 5204. 병합 정렬

5204. 병합 정렬

---

문제)

 

알고리즘 교수님은 학생들에게 병합 정렬을 이용해 오름차순으로 정렬하는 과제를 내려고 한다.

정렬 된 결과만으로는 실제로 병합 정렬을 적용했는지 알 수 없기 때문에 다음과 같은 제약을 주었다.

N개의 정렬 대상을 가진 리스트 L을 분할할 때 L[0:N//2], L[N//2:N]으로 분할 한다.

병합 과정에서 다음처럼 왼쪽 마지막 원소가 오른쪽 마지막 원소보다 큰 경우의 수를 출력한다.

 

 

정렬이 끝난 리스트 L에서 L[N//2] 원소를 출력한다.

알고리즘 교수님의 조건에 따라 병합 정렬을 수행하는 프로그램을 만드시오.

 

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 정수의 개수 N이 주어지고, 다음 줄에 N개의 정수 ai가 주어진다.

5<=N<=1,000,000, 0 <= ai <= 1,000,000

 

 

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤,  N//2 번째 원소와 오른쪽 원소가 먼저 복사되는 경우의 수를 출력한다.

 

 

 

 

 

풀이)

 

# 일반적인 pop(0)를 사용하면 시간초과가 났다.
from collections import deque
 
def merge(left, right):
    
    global cnt
    # 병합하여 담을 result
    result = deque()
 
    # 문제에서 주어진 조건
    if left[-1] > right[-1]:
        cnt += 1
    
    # left, right가 모두 사라질 때까지
    while len(left) > 0 or len(right) > 0:
        # 둘 다 남아있는 경우
        if len(left) > 0 and len(right) > 0:
            # 두 값을 비교해 크기순으로 result에 넣어준다.
            if left[0] <= right[0]:
                result.append(left.popleft())
            else:
                result.append(right.popleft())
                
        # 어느한쪽이 다 없어진 경우
        elif len(left) > 0:
            result.append(left.popleft())
        elif len(right) > 0:
            result.append(right.popleft())
    return result
 
 
# 병합정렬을 위해서 리스트를 다 쪼개기
def merge_sort(li):
    if len(li) == 1:
        return li
    
    # 쪼개서 넣을 deque만들기
    left = deque()
    right = deque()
    mid = len(li) // 2
 
    # 나눠지지 않을 때까지 쪼개는 과정
    for i in range(mid):
        left.append(li[i])
    for i in range(mid, len(li)):
        right.append(li[i])
 
    left = merge_sort(left)
    right = merge_sort(right)
 
    # 다 쪼개졌으면 병합을 시작한다.
    return merge(left, right)
 
T = int(input())
for _ in range(T):
    n = int(input())
    li = list(map(int, input().split()))
    cnt = 0
    print(f"#{_ + 1} {merge_sort(li)[n // 2]} {cnt}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.