[SWEA D3] 5204. [파이썬 S/W 문제해결 구현] 4일차 - 병합 정렬 Python

문제출처> 5204. [파이썬 S/W 문제해결 구현] 4일차 - 병합 정렬

🚩 문제설명

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

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

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 번째 원소와 오른쪽 원소가 먼저 복사되는 경우의 수를 출력한다.

---

입력

2
5
2 2 1 1 3
10
7 5 4 1 2 10 3 6 9 8

출력

#1 2 0
#2 6 6

---

🤔 처음에 시간 초과가 되었던 문제코드

---

def partition(lst):

    if len(lst) <= 1:
        return lst
    mid = len(lst)//2
    left_lst = partition(lst[:mid])
    right_lst = partition(lst[mid:])
    return merge(left_lst, right_lst)


def merge(left_lst, right_lst):
    global cnt
    result = []

    if left_lst[-1] > right_lst[-1]:
        cnt += 1

    while len(left_lst) > 0 or len(right_lst) > 0:
        if len(left_lst) > 0 and len(right_lst) > 0:
            if left_lst[0] <= right_lst[0]:
                result.append(left_lst[0])
                left_lst = left_lst[1:]
            else:
                result.append(right_lst[0])
                right_lst = right_lst[1:]

        elif len(left_lst) > 0:
            result.append(left_lst[0])
            left_lst = left_lst[1:]
        elif len(right_lst) > 0:
            result.append(right_lst[0])
            right_lst = right_lst[1:]

    return result


T = int(input())

for test_case in range(1, T + 1):
    cnt = 0
    N = int(input())
    lst = list(map(int, input().split()))
    Data = partition(lst)

    print(f'#{test_case} {Data[N//2]} {cnt}')

---

** 시간 초과가 되었던 이유는 파이썬 리스트의 len(), append() 연산자 때문이였다. 이 두가지 연산자를 다른 방식으로 대체하여 푸니 통과가 되었다!

📝 문제풀이

---

def partition(lst):

    if len(lst) <= 1:
        return lst
    mid = len(lst)//2
    left_lst = partition(lst[:mid])
    right_lst = partition(lst[mid:])
    return merge(left_lst, right_lst)


def merge(left_lst, right_lst):
    global cnt
    left_N = len(left_lst)
    right_N = len(right_lst)
    result = [0]*(left_N+right_N)
    left_i, right_i = 0, 0
    i = 0
    if left_lst[-1] > right_lst[-1]:
        cnt += 1

    while left_i < left_N or right_i < right_N:
        if left_i < left_N and right_i < right_N:
            if left_lst[left_i] <= right_lst[right_i]:
                result[i] = left_lst[left_i]
                i += 1
                left_i += 1
            else:
                result[i] = right_lst[right_i]
                i += 1
                right_i += 1

        elif left_i < left_N:
            result[i] = left_lst[left_i]
            i += 1
            left_i += 1
        elif right_i < right_N:
            result[i] = right_lst[right_i]
            i += 1
            right_i += 1
    #print(result)
    return result


T = int(input())

for test_case in range(1, T + 1):
    cnt = 0
    N = int(input())
    lst = list(map(int, input().split()))
    Data = partition(lst)

    print(f'#{test_case} {Data[N//2]} {cnt}')

---

🔧 해결방법

1. 재귀로 중간값을 구해 왼쪽, 오른쪽을 리스트에 원소가 1개 들어있을때까지 나눈다.
   
   
2. 다 나누면 제일 왼쪽 아래쪽 부터 합쳐가며 result리스트에 정렬해나가며 합병한다.
   
   
3. merge(합병) 하는 중에 왼쪽 리스트의 마지막 숫자가 오른쪽 마지막 숫자보다 크면 cnt+=1 해준다.
   
   
4. 작은 리스트 부터 차례대로 정렬해 나가면서 재귀로 점점 큰 리스트를 만들어 합병해 나간다.