[알고스팟] MEASURETIME - 삽입 정렬 시간 재기 (C++)

문제

 

https://www.algospot.com/judge/problem/read/MEASURETIME

algospot.com :: MEASURETIME

 

 

풀이

 

종만북 난이도: 중

 

세그먼트 트리와 같은 기능을 하지만 비트 연산을 이용해 좀 더 간단히 구현이 가능한 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(binary indexed tree)로 해결하는 문제이다.

 

펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는 데 특화되어 있다.

만약 [3,7] 구간의 값을 구하고 싶다면  [1,7] 부분 합에 [1,2] 부분 합을 빼주는 것으로 간단히 구현할 수 있다.

 

깔끔한 설명은 백준님의 게시글을 참고하자.

펜윅 트리 (바이너리 인덱스 트리) - baekjoon

 

 

이번 문제에서는 삽입 정렬 때의 새로운 원소가 추가될 때마다 이동하는 횟수를 구해야 한다.

새로운 원소의 이동 횟수는 기존의 정렬된 배열에서 해당 원소보다 큰 원소의 개수가 된다.

예를 들어 1, 3, 4, 5에서 2를 추가한다면 결국 자신보다 큰 3, 4, 5와 swap해야 하므로 3번의 이동을 해야 한다.

 

문제에서 주어지는 원소는 0 이상 1,000,000 미만이므로 각 원소들의 등장 횟수를 해당 구간에 저장하자.

새로운 원소가 n이라면 현재 정렬된 배열에서 n보다 큰 원소의 개수는 최대 원소의 값이 될 수 있는  999,999보다 작은 원소들의 개수에서 n보다 작은 원소들의 개수를 빼 주면 된다.

펜윅 트리에는 각 원소의 등장 횟수가 저장되어 있으므로, 1 이상 n이하의 원소의 개수는 [1, n] 구간의 합이다.

이를 계산해주는 함수를 Sum(n)이라고 하자.

그렇다면 새로운 원소 n의 정렬에 필요한 이동 횟수는

Sum(999,999) - Sum(n)이 된다.

 

단! 펜윅트리는 1에서부터 시작하는 구간을 계산할 수 있도록 최적화되어있으므로 본인은 모든 원소 값을 +1 하여 문제를 해결하였다.

따라서 이동 횟수는 Sum(1,000,000) - Sum(n+1)로 계산하였다.

또한 모든 수들의 삽입 정렬 시의 이동 횟수는 int형의 범위를 초과할 수 있으므로 long long형을 사용해주자. 

 

 

 

코드