[분할정복] 백준 - 버블 소트 1517번

버블 소트 1517번

👏 key point

* 데이터 입력과 그에 따른 시간복잡도

• O(N^3)$ 알고리즘: 크기 2560인 입력까지를 1초 안에 풀 수 있습니다. 이때 $2560^3$은 대략 16억입니다.

• O(N^2)$ 알고리즘: 크기 40960인 입력까지를 1초 안에 풀 수 있습니다. 이때 $40960^2$은 대략 16억입니다.

• O(N \lg N)$ 알고리즘: 크기가 대략 2천만인 입력까지를 1초 안에 풀 수 있습니다. 이때 $N \lg N$은 대략 5억입니다.

• O(N)$ 알고리즘: 크기가 대략 1억 6천만인 입력까지를 1초 안에 풀 수 있습니다.

  따라서 버블 소트는 단순하게 이중 포문으로 일일이 하나씩 비교를 한다면 쉽게 풀 수 있지만 시간복잡도 문제로 불가능 하다. 따라서 우리는 nlogn 의 시간복잡도로 풀 수 있는 병합정렬을 이용해 버블 소트를 풀려고 할 것이다.

[1256][3478]

이렇게 병합 정렬에 의해 분해된 두 리스트가 있다고 하자 이 두 리스트를 병합하기 위해서 두 리스트의 목록을 비교하는데 만약 오른쪽에 있는 리스트 값이 새로운 리스트에 들어온다고 한다면 cnt += 1을 해준다. (바꿔줘야 하므로) 그리고 왼쪽에 있는 리스트가 새로운 리스트에 들어온다면 result += cnt를 해준다.

따라서 하나의 숫자 당 swap 해줘야 하는 개수를 cnt라고 보면 된다.

예를 들어
12가 들어오고 (이때, 자리 변화가 없으므로 cnt = 0, result = 0)

[1,2]

3과 4 가 5,6 보다 작으니까 34가 들어 온다.

[3,4]

(이때, 5,6이 원래 자리 보다 밀려 났으므로 cnt = 2, result = 0)
다시 5,6이 들어오려고 할 때는 원래 자리 보다 2만큼 밀려났으므로(cnt = 2)
그만큼 더 해줘야한다. (result += cnt)

[1,2,3,4,5,6]

뒤에 있는 7,8은 swap을 하지 않는다.

답 : 4

🎂 코드

n = int(input())

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

result = 0

def srt(lst):
    global result
    #lst의 길이가 1이 될 때까지 분할
    if len(lst) <= 1:
        return lst

    #분할
    a = srt(lst[:len(lst) // 2])
    b = srt(lst[len(lst) // 2:])
    
    #병합
    i = 0
    j = 0
    cnt = 0

    #매 순간마다 정렬하기 위해 리셋
    merg = []

    while i < len(a) and j < len(b):
        #왼쪽 리스트의 값이 들어올 때
        if a[i] <= b[j]:
            merg.append(a[i])
            i += 1
            
            result += cnt
        #오른쪽 리스트의 값이 들어올 때    
        else:
            merg.append(b[j])
            j += 1
            cnt += 1
    
    #두 리스트 중 한 리스트의 값이 모두 소진 되었을 때
    while i < len(a):
        merg.append(a[i])
        result += cnt
        i += 1

    while j < len(b):
        merg.append(b[j])
        j += 1
        
    return merg  


srt(lst)
    
print(result)