백준 [ALGORITHM] - 버블 소트 (1517)

import sys

input = sys.stdin.readline

N = int(input().strip())
arr = []
arr = list(map(int, input().split()))
count = 0
    
def merge_sort(arr):
    if len(arr) <= 1: 
        return arr
        
    mid = len(arr) // 2
    lefts = merge_sort(arr[:mid])
    rights = merge_sort(arr[mid:])

    return merge(lefts, rights)

def merge(lefts, rights):
    result = []
    global count
    i = j = 0

    while i < len(lefts) and j < len(rights):
        if lefts[i] <= rights[j]:  
            result.append(lefts[i])
            i += 1
        else:
            result.append(rights[j])
            count += len(lefts) - i
            j += 1
    
    result.extend(lefts[i:])
    result.extend(rights[j:])

    return result
    
ans = merge_sort(arr)
print(count)

 

플레5 문제 풀어봤다. 

문제 이름 처럼 버블 소트를 사용해서 풀면 시간초과로 풀지 못하고, 병합 정렬을 이용해서 풀면 풀린다.

요즘 소트 공부 중인데 개념은 쉽지만 응용을 하려니까 머리가 아프다.

 

이 문제는 역순쌍이라는 개념을 이용해서 좌측에 있는 배열에 i<j인 상황에서 좌측 배열의 A[i:]의 길이 값이 swap한 숫자가 되기에 이를 이용해서 풀었다.