[백준] 1517번 : 버블소트

1517번: 버블 소트

1517번: 버블 소트

🤔 문제분석

처음 문제에 접근할때 배열을 순회하면서, 배열의 인덱스의 오른쪽 부분의 배열들이 현재의 배열의 값보다 큰 개수를 세어 카운팅을 하여 문제를 풀었습니다.

해당 문제를 해결하기위해서는 병합정렬을 알아야합니다. 병합정렬은 분할정복 알고리즘으로 가장 작은 단위(풀기쉬운문제)로 분할하고, 원하는 조건으로 정복(병합) 합니다.

병합하는 과정에서 버블소트 swap 횟수를 알 수 있습니다.

병합하고자 하는배열에 오른쪽에 있는 배열을 추가할때, “왼쪽에 있는 배열의 수 - 추가된 왼쪽 배열의 수” 만큼 swap 됩니다.

아래의 그림에서 1와 2를 병합하고자 하는 배열에 추가할때, [3,4]의 길이인 2만큼 추가가 됩니다.

📝 의사코드

1. 병합 정렬을 한다.
   1. 병합할때에, 오른쪽 배열이 새로운 병합될 배열에 추가될때, 남아 있는 left 배열과 swap 해야한다.
   2. 왼쪽배열의 수 - 왼쪽배열을 수 의 가중치를 더한다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())

data = list(map(int, input().split()))

def merge(left, right):
    global ans
    l, r = 0, 0
    temp = []
    while l < len(left) and r < len(right):
        if left[l] > right[r]:
            temp.append(right[r])
            r += 1
            ans += len(left) - l
        else:
            temp.append(left[l])
            l += 1
    
    if l == len(left):
        temp.extend(right[r:])
    else:
        temp.extend(left[l:])
    
    return temp

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

ans = 0
merge_sort(data)
print(ans)

🎯 피드백 및 개선사항

병합정렬의 아이디어를 떠올리는것이 문제의 포인트라고 생각한다.

병합정렬과 버블정렬이 어떻게 정렬되는지 다시한번더 되짚어보는 시간이 되었습니다.

❓다른사람은 어떻게 풀었을까

다른 풀이들도 병합정렬을 활용하여 문제를 해결하였습니다.