[백준] 1517번 버블 소트 ★★

💡문제접근

• 처음엔 문제 그대로 버블 정렬을 구현하여 Swap이 발생할때마다 Swap 횟수를 카운트하는 방식으로 코드를 작성했는데 시간초과(TLE)가 발생해서 질문게시판의 내용을 참고했다. 버블 정렬은 O(N^2) 시간복잡도를 가지는데 이걸 그대로 사용한다면 시간초과가 발생하는게 당연하다고 알려주었고 다른 분할 정복 알고리즘인 병합 정렬을 사용해야한다고 나와있었다. 그래서 병합 정렬을 코드로 작성하여 문제를 해결했다.

💡코드(메모리 : 90308KB, 시간 : 2004ms)

import sys
input = sys.stdin.readline

def merge_sort(arr):
    if len(arr) <= 1:
        return arr, 0
    else:
    	# recursion을 이용해 배열 분할
        left, inv_count_left = merge_sort(arr[:len(arr)//2])
        right, inv_count_right = merge_sort(arr[len(arr)//2:])
        
        # 반으로 나눈 배열을 병합
        merged, inv_count_merge = merge(left, right)
	
    inv_count = inv_count_left + inv_count_right + inv_count_merge
    return merged, inv_count

def merge(left_arr, right_arr):
    merged = []
    inv_count = 0
    i = j = 0

    while i < len(left_arr) and j < len(right_arr):
    	# 왼쪽 배열의 값보다 오른쪽 배열의 값이 더 크다면?
        if left_arr[i] <= right_arr[j]:
        	# 병합된 배열에는 왼쪽 배열의 값이 먼저 저장
            merged.append(left_arr[i])
            i += 1
        # 왼쪽 배열의 값이 오른쪽 배열의 값보다 더 크다면?
        else:
        	# 병합된 배열에는 오른쪽 배열의 값이 먼저 저장
            merged.append(right_arr[j])
            j += 1
            inv_count += len(left_arr) - i

	# 병합된 배열에 저장되지 못한 배열의 나머지 원소들도 넣어줌
    while i < len(left_arr):
        merged.append(left_arr[i])
        i += 1

    while j < len(right_arr):
        merged.append(right_arr[j])
        j += 1

    return merged, inv_count

N = int(input())
arr = list(map(int, input().strip().split()))
merged_arr, swap = merge_sort(arr)
# print(merged_arr)
print(swap)

💡소요시간 : 57m