백준 10090번 Counting Inversion

문제 링크입니다: https://www.acmicpc.net/problem/10090

10090번: Counting Inversions

얼핏 보기에는 시간복잡도 O(N^2)으로 쉽게 풀 수 있는 문제처럼 보이지만 N이 무려 100만이기 때문에 N^2으로 풀 경우 TLE가 발생합니다.

보통 1초에 대략 1억 번의 계산이 가능하다고 가정하므로 시간복잡도 O(NlogN) 안에 풀 수 있는 풀이법을 떠올려야 했습니다. 따라서, 여러 알고리즘을 떠올린 결과 합병 정렬 즉, Merge Sort가 적당하다고 생각했고 아래와 같이 알고리즘을 작성했습니다.

1. 우선 배열을 반으로 나누어 왼쪽 부분 배열, 오른쪽 부분 배열로 나눕니다.

2. 정렬을 진행할 때 왼쪽부터 진행하므로 왼쪽 부분 배열의 모든 원소들이 오른쪽 부분배열의 모든 원소들보다 왼쪽에 있다는 것이 자명합니다.

3. 따라서, 분할한 원소들을 다시 합병 즉, merge를 시킬 때 오른쪽 부분배열의 원소가 왼쪽 부분배열의 원소보다 작아 합쳐지는 배열로 들어갈 때, 왼쪽 부분 배열에 아직 남아있는 원소들이 현재 합쳐지는 오른쪽 부분 배열의 원소보다 크다는 것이 증명됩니다. (cnt += leftVSize - leftIdx; 를 하는 이유)

4. 1 ~ 3번 과정을 부분 배열의 크기가 1일 때까지 진행합니다. (Merge Sort는 크기가 1인 부분 배열까지 쪼갠 뒤 다시 합치므로)

 

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~