백준 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 횟수를 출력한다

문제 답안 

먼저 이 문제를 버블정렬 방식으로 일일이 정렬하며 카운트를 구할 경우, 아시다시피 시간복잡도는 O(N^2)이 된다. N의 범위는 50만이며, N^2의 시간복잡도를 가진 알고리즘으로 접근 시, 2.5억번의 값이 필요하므로 가뿐히 시간초과가 된다. 따라서 이 문제는 최소 nlogn의 시간복잡도를 가진 알고리즘으로 구현해야 한다. 

해당 문제를 트리로 풀 수 있는지를 검토 하기 위해 공간복잡도를 계산해본다. N은 500,000으로 현재 구성된 값을 세그먼트 트리, 혹은 완전 이진트리로 가정했을 때 메모리를 계산해보면 (500,000 * 4) / (1,024 * 1,024)로 1.9MB의 값이 필요한 것으로 예상된다. (메모리 계산은 제가 이런 쪽에 약해 정확하지 않을 수 있습니다)

위의 계산을 통해서 nlogn의 시간복잡도를 가진 트리로 풀 수 있다는 결론이 된다. 따라서, 해당 문제를 병합정렬의 알고리즘에 약간의 기술(?)을 넣어서 푸는 방식으로 접근했다. 

간단하게 아래의 예를 생각하면서 나는 문제를 접근했다. 

그룹	왼쪽 그룹				오른쪽 그룹
Index	0	1	2	3	4	5	6	7
초기 배열	1	4	6	9	2	3	7	8

위와 같은 배열이 있다고 가정 했을 때, 병합 정렬 알고리즘을 이용해서 문제를 해결해나가는 과정을 이해해본다. 

그룹	왼쪽 그룹				오른쪽 그룹
Index	0	1	2	3	4	5	6	7
초기 배열	1	4	6	9	2	3	7	8
정렬된 배열	1	2	3	4	6	7	8	9
SWAP 횟수		3번 (4-1)	3번 (5-2)			1번 (6-5)	1번 (7-6)

0, 4번 인덱스를 비교하면 0이 정렬된 배열의 0번 인덱스에 와야한다는 것을 알 수 있다. 그 다음에는 1,4 인덱스를 비교해보면 4가 정렬된 배열의 1번째 자리에 와야한다는 것을 알 수 있다. 이 때, 4번이 2번 자리에 오기 위해서 Swap을 해야하는 횟수는 3(4-1)으로 구할 수 있다. 그 다음으로는 1과 5 인덱스를 비교해야하는데, 5번 인덱스에 있는 3이 정렬된 배열의 2번 인덱스에 와야한다는 것을 알 수 있다. 이 값은 3번(5-2)이다. 

즉, 위의 과정에서 병합된 정렬을 구하는 과정에서 인덱스 정보를 추가하고 그 값을 적절히 활용하는 것만으로 몇번의 Swap을 해야한다는 것을 정확하게 파악할 수 있음을 알 수 있게 되었다. 따라서, 실제 문제를 풀 때는 병합정렬을 구현하고, 병합정렬의 Swap 함수 내에서 인데스 정보를 추가하고 적당히 연산을 넣어주는 방법을 취하면 된다. 

내가 작성한 코드는 아래와 같다.

import sys
def devide(l,r) : 
    if l == r :
        return
    mid = (l + r)//2
    devide(l,mid)
    devide(mid+1,r)
    swap(l,mid,mid+1,r)
    return

def swap(ll,lr,rl,rr) :
    global swap_cnt
    temp_list = []
    start_idx = ll #이 변수는 현재 temp_list의 위치를 알려주는 값으로 보면 된다. 0이나 temp_list의 길이로 하지 않는 이유는 ll이 0부터 시작하지 않기 때문이다. 
    si,li = ll,rr #si : start_index의 줄임말. li : last_index의 줄임말. 둘다 원래 배열에 값을 넣을 때 사용한다. 
    while ll <= lr and rl <= rr : #좌,우 배열 중 한쪽 배열이 temp_list에 다 들어갈 때까지 값을 비교한다.
        if my_list[ll] > my_list[rl] : #오른쪽 배열에 있는 값을 temp_list에 집어넣는다.
            temp_list.append(my_list[rl])
            swap_cnt += (rl-start_idx)
            rl +=1 #
            start_idx +=1 
        else :
            temp_list.append(my_list[ll])
            ll += 1
            start_idx += 1
    while ll <= lr : #만약 왼쪽 배열이 temp_list로 덜 들어갔다면, 다 넣어준다.
        temp_list.append(my_list[ll])
        ll +=1
    while rl <= rr : #만약 오른쪽 배열이 temp_list로 덜 들어갔다면, 다 넣어준다.
        temp_list.append(my_list[rl])
        rl += 1
    for z in range(li,si-1,-1) : #temp_list에 넣어준 값을 하나씩 원래 배열로 넣어서 정렬시켜준다.
        my_list[z] = temp_list.pop()
    return


t = int(sys.stdin.readline().rstrip())
my_list = list(map(int,sys.stdin.readline().split()))
swap_cnt = 0
devide(0,len(my_list)-1)
print(swap_cnt)