문제

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 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

www.acmicpc.net/problem/1517

  • 입력

첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.

  • 출력

첫째 줄에 Swap 횟수를 출력한다

과정

병합정렬이라고는 생각했는데 그래서 어떻게 swap 횟수를 구해야할지 모르겠어서 방법을 찾아봤다. 그래도 병합정렬까지 생각한 게 어디야..

아래는 내가 짠 코드인데 시간 초과가 떴다.

import sys

def mergesort(s, e):
    global cnt

    if e-s == 1:
        return arr[s:e]

    mid = (s + e) // 2
    left = mergesort(s, mid)
    right = mergesort(mid, e)
    res = []

    while left and right:
        if left[0] <= right[0]:
            res.append(left.pop(0))
        elif left[0] > right[0]:
            res.append(right.pop(0))
            cnt += len(left)

    while left:
        res.append(left.pop(0))
    while right:
        res.append(right.pop(0))

    return res

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
mergesort(0, n)
print(cnt)

원래 있는 배열을 바꾸는 것 보다 새 배열을 만들어서 푸는 게 더 코드가 간단해서 그렇게 풀었는데 아무래도 append랑 pop이 많이 쓰이다보니 시간이 초과된 것 같다.

아니 갈수록 시간 맞추기가 너무 어렵잖아? 사실상 내용은 똑같은데.. 거참

최종코드

import sys

def mergesort(s, e):
    global cnt

    if e-s == 1:
        return

    mid = (s + e) // 2
    mergesort(s, mid)
    mergesort(mid, e)

    left = s
    right = mid
    tmp = []

    while left < mid and right < e:
        if arr[left] <= arr[right]:
            tmp.append(arr[left])
            left += 1
        elif arr[left] > arr[right]:
            tmp.append(arr[right])
            right += 1
            cnt += mid - left

    if left < mid:
        tmp += arr[left:mid]
    elif right < e:
        tmp += arr[right:e]

    for i in range(e - s):
        arr[s+i] = tmp[i]

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
mergesort(0, n)
print(cnt)

새로운 배열을 만들지 않고 원래 있던 배열을 바꾸면서 푸는 코드이다.

인덱스를 더 신경써야해서 귀찮지만 어쨌든 pop이랑 append를 많이 안 써서 빠르다. 앞으로 유의해서 풀어야겠다.

참고 사이트