[백준/1517] 버블 소트 (Python)

Problem : https://www.acmicpc.net/problem/1517

1517번: 버블 소트

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:22:04

 

---

 

문제 설명

 

 

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

 

입력 예시

 

3
3 2 1

 

출력 예시

 

3

 

 

---

 

풀이

 

 

버블 소트 방식 그대로 구현하면 O(N^2)의 시간복잡도가 소요되므로, 우리는 우회로를 찾을 필요가 있다.

 

여러 풀이가 있겠지만(문제 풀고서야 다른 분들 코드를 뜯어보면서 알게되었다) 나는 분할 정복을 이용하기로 했다. 머지 소트 방식대로 정렬을 수행하면 O(NlogN)의 시간복잡도가 소요되며, 이 때 버블 소트와 머지 소트의 차이를 이용해 볼 수 있겠다.

 

부분적으로 합병할 때, 왼쪽 배열의 현재 원소와 오른쪽 배열의 현재 원소를 비교하게 된다. 왼쪽 배열 원소가 같거나 작을 때는 버블 소트 상으로 아무런 일도 일어나지 않지만, 오른쪽 배열 원소가 작을 때는 오른쪽 원소가 앞으로 오면서 왼쪽 배열 원소들과 swap이 일어나게 된다. 그 횟수는 배치되지 않고 남은 왼쪽 배열 원소의 개수가 될 것이다.

 

이런 식으로 머지 소트를 수행하면, 그 부분 합병에서 일어나는 swap을 전부 계산할 수 있겠다.

 

 

풀이 코드

N = int(input())
num_list = list(map(int, input().split()))

def div_and_conquer(start, end) :
  if start == end :
    return 0

  mid = (start + end) // 2
  lval = div_and_conquer(start, mid)
  rval = div_and_conquer(mid+1, end)
  
  val, lst = lval + rval, list()
  l, r = start, mid+1 
  while l <= mid and r <= end :
    if num_list[l] <= num_list[r] :
      lst.append(num_list[l])
      l += 1
    else :
      lst.append(num_list[r])
      r += 1
      val += mid - l + 1

  if l <= mid :
    for i in range(l, mid+1) :
      lst.append(num_list[i])
  if r <= end :
    for i in range(r, end+1) :
      lst.append(num_list[i])

  for i in range(start, end+1) :
    num_list[i] = lst[i-start]

  return val

print(div_and_conquer(0, N-1))

풀이 완료!