[백준/10090] Counting Inversions (Python)

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

10090번: Counting Inversions

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:44:26

 

---

 

문제 설명

 

 

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Write program invcnt that computes the number of the inversions in a given permutation.

 

1부터 n까지의 정수가 정확히 한 번씩 등장하는 a1, a2, ..., an 수열 순열이 주어집니다.

 

이 순열의 두 정수가, 앞선 정수가 뒤의 정수보다 더 크다면 역전을 형성합니다.

 

예를 들어, 순열 4 2 7 1 5 6 3에는  4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3  총 10개의 역전이 존재합니다.

 

순열이 주어졌을때, 역전의 개수를 계산하는 프로그램을 작성하세요.

 

 

입력 및 출력

 

입력

 

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces.

 

표준 입력으로 첫째 줄에 숫자의 수 N이 주어집니다. 두 번째 줄에는 순열을 이루는 N개의 수가 공백으로 구분되어 주어집니다.

 

출력

 

Write the count of inversions on the standard output.

 

역전 현상 개수를 표준 출력으로 작성하세요.

 

입력 예시

 

7
4 2 7 1 5 6 3

 

출력 예시

 

10

 

 

---

 

풀이

 

처음에는 많이 해맸다. 어제 풀었던 방식으로 세그먼트 트리로 도전해 보기도 했지만 시간 초과를 피할 수 없었다 (즉 업데이트를 시켜가면서 경우의 수 찾기).

 

결국 검색의 힘을 쪼금 빌렸는데... 핵심은 이 문제와 동일했다.

 

2023.11.23 - [알고리즘 문제/백준] - [백준/1517] 버블 소트 (Python)

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

 

즉 병합 정렬을 수행하면서, r번째 오른쪽 부분 리스트가 l번째 왼쪽 부분리스트보다 작다면 남은 부분 리스트와 역전 현상을 이루므로 이를(mid - l + 1) 더해주는 방식이다.

 

풀이 코드

import sys
input = sys.stdin.readline

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

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

  mid = (start + end) // 2
  left = div_and_conqure(start, mid)
  right = div_and_conqure(mid+1, end)
  result = 0
  
  l, r = start, mid+1
  temp = list()
  while l < mid+1 and r < end+1 :
    if num_list[l] < num_list[r] :
      temp.append(num_list[l])
      l += 1
    else :
      temp.append(num_list[r])
      r += 1
      result += mid - l + 1

  for i in range(l, mid+1) :
    temp.append(num_list[i])
  for i in range(r, end+1) :
    temp.append(num_list[i])
  for i in range(end - start + 1) :
    num_list[i+start] = temp[i]

  return result + left + right

print(div_and_conqure(0, N-1))

풀이 완료!