[백준/파이썬] 1517 버블 소트

[백준/파이썬] 1517 버블 소트

 

📌 문제 

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다.

다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

 

 

⚔ 입력

첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.

 

 

📣 출력

첫째 줄에 Swap 횟수를 출력한다

 

 

 

---

 

 

 

💎 문제분석하기

 

문제 이름은 버블소트지만 사실은 버블 소트 로직으로 풀 수 없다. 병합 소트의 과정에서 버블 소트가 발생하는 지점을 포착해내는 방식으로 풀어야 한다. 

 

자바 병합 소트 로직보다 파이썬 로직이 훨씬 쉽게 다가온다. 

 

버블 소트가 일어나는 과정에서 카운트 되는 공식이 발생하는데 그것에 착안하여 풀이한다. 

 

 

 

 

 

 

 

💡 코드 구현하기

 

 

73%에서 계속 실패 뜬 로직 

=> mid를 len // 2로 직관적으로 구해놓고 처리한 로직이라 중복이 나왔을 때 계산이 중첩되면서 걸렸을 것 같다.  

 

 

import sys

def merge_sort(arr):
    global swap_cnt
    
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2 
    print(mid)

    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    # global new_arr
    new_arr = []
    l = h = 0
    
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            new_arr.append(low_arr[l])
            l += 1
        else:
            new_arr.append(high_arr[h])
            h += 1
            swap_cnt += mid - l 
            
    new_arr += low_arr[l:]
    new_arr += high_arr[h:]
    
    return new_arr

if __name__ == "__main__":
    swap_cnt = 0
    N = int(sys.stdin.readline())
    ARR = list(map(int, sys.stdin.readline().split()))
    merge_sort(ARR)
    print(swap_cnt)

 

 

 

 

따라서 m을 length를 기준으로 카운트 하는 방식 (짝수 기준)이 아니라 

start와 end의 지점을 기준으로 (홀수 기준) 카운트 하는 방식으로 산출하여야 하고 

예시의 경우를 대입해보면 

 

 

 

 

divide가 진행되고 다시 m이 레벨로 돌아오기 까지 swap이 발생하지 않으므로 3레벨에서 진행되는 swap을 카운트해보면 위와 같다. 

 

 

 

import sys

def merge_sort(start, end):
    global swap_cnt, ARR

    if start < end:
        mid = (start + end) // 2
        merge_sort(start, mid)
        merge_sort(mid + 1, end)

        low_idx, high_idx = start, mid + 1
        new_arr = []

        # 비교를 통해 swap을 하는 부분은 다음 비교를 위해 idx를 올려준다 
        while low_idx <= mid and high_idx <= end:
            if ARR[low_idx] <= ARR[high_idx]:
                new_arr.append(ARR[low_idx])
                low_idx += 1
            else:
                new_arr.append(ARR[high_idx])
                high_idx += 1
                swap_cnt += mid - low_idx + 1  # 버블 swap 카운팅 

        if low_idx <= mid:
            new_arr = new_arr + ARR[low_idx : mid + 1]
        if high_idx <= end:
            new_arr = new_arr + ARR[high_idx : end + 1]

        for i in range(len(new_arr)):
            ARR[start + i] = new_arr[i]


if __name__ == "__main__":
    swap_cnt = 0
    N = int(sys.stdin.readline())
    ARR = list(map(int, sys.stdin.readline().split()))
    merge_sort(0, N - 1)
    print(swap_cnt)

 

 

 

---