백준 불만 정렬(5012)

불만 정렬

1. 힌트

1) 구간 합을 나타내는 세그먼트 트리를 통해서 Inversion의 개수를 셀 수 있다.

2) 어떤 Inversion $a_i,\ a_j(a_i > a_j, i > j)$의 오른쪽에 $a_k(a_j > a_k)$가 위치한다면 $a_i,\ a_j,\ a_k$는 조건을 만족한다.

3) $I[i]$를 어떤 Inversion $(a_i,\ a_j)$에서 $S[i]$가 $a_j$인 Inversion의 개수로 정의하면 Inversion을 구하는 방식과 마찬가지로 이 또한 구할 수 있다.

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

백준 버블 소트(1517)

버블 소트는 인접한 두 원소를 바꿔주는 정렬 방법이었는데 이렇게 세 원소를 골라주는 방법은 어떨까?
문제의 조건이 비슷하므로 Inversion을 구하는 과정과 비슷하게 풀 수 있을 것 같다.

2) 순서를 강제할 수 있을까?

$I[x] = S[x]$가 가지고 있는 Inversion의 수
이렇게 정의하자. 단, $a_i,\ a_j$쌍에서 $S[x]$가 $a_j$라고 해서 중복으로 세지지 않게 하자.
즉, $I[x]$는 $S$에서 $S[x]$보다 왼쪽에 있으면서 $S[x]$보다 큰 순서쌍의 개수이다.

예를 들어 $N=4, S=[3,3,2,1]$이라면 $I = [0,0,2,3]$이다.
여기에 $a_k$까지 추가해서 우리가 구하고자 하는 세 원소를 구해보자. $S[k]$보다 왼쪽에 있는 Inversion의 개수들을 모두 더하면 조건을 만족하는 순서 쌍의 개수를 모두 구할 수 있다. 가능한 모든 경우를 세기 위해서는 가장 작은 $S[k]$부터 찾아봐야하는데, 두 원소의 값이 같은 경우가 있으므로 그런 경우는 같은 원소중에서 더 왼쪽에 있는 것 부터 먼저 체크해주도록 하자.

3. 구현

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] S = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		// P[x] = S의 원소 x의 위치 (작은 순으로)  
		ArrayList<PriorityQueue<Integer>> P = new ArrayList<>();
		for (int i = 0; i <= N; i++) P.add(new PriorityQueue<>());
		for (int i = 0; i < N; i++) P.get(S[i]).add(i + 1);
		long[] I = new long[N + 1]; // S[i]가 가지고 있는 Inversion의 개수 저장
		FenwickTree t = new FenwickTree(N); // S[i]가 존재하는지 여부
		for (int i = 1; i <= N; i++) t.add(i, 1);
		// I[i]를 만든다
		for (int i = 1; i <= N; i++) {
			PriorityQueue<Integer> pq = P.get(i);
			// PriorityQueue를 순회하기 위해 임시로 만듬
			PriorityQueue<Integer> temp = new PriorityQueue<>();
			while (!pq.isEmpty()) {
				int x = pq.poll();
				// t에 남아있는 모든 원소는 S[x]보다 같거나 크고,
				// 같은 원소들은 S[x]보다 오른쪽에 있으므로
				// 구간 합 t[x] - 1은 Inversion의 개수가 된다.
				I[x] = t.sum(x) - 1;
				t.add(x, -1);
				temp.offer(x);
			}
			P.set(i, temp);
		}
		long sum = 0;
		t = new FenwickTree(N);
		for (int i = 1; i <= N; i++) t.add(i, I[i]);
		for (PriorityQueue<Integer> pq : P) {
			while (!pq.isEmpty()) {
				int x = pq.poll();
				sum += t.sum(x - 1);
				t.add(x, -(t.sum(x) - t.sum(x - 1)));
			}
		}
		System.out.println(sum);
	}
	
}

class FenwickTree {
	long[] tree;
	
	FenwickTree(int n) { tree = new long[n + 1]; }
	
	void add(int pos, long val) {
		while (pos < tree.length) {
			tree[pos] += val;
			pos += (pos & -pos);
		}
	}
	
	long sum(int pos) {
		long ret = 0;
		while (pos > 0) {
			ret += tree[pos];
			pos -= (pos & -pos);
		}
		return ret;
	}
	
}

1) 시간 복잡도

$N$개의 원소들에 $lgN$의 연산을 하므로 $O(NlgN)$

2) 테스트 케이스

100000
100000 99999 99998 ... 3 2 1
->166661666700000

현주가 만든 불만 정렬은 10만개의 원소를 정렬하는데 이만큼 비교를 해야한다... 이 테스트 케이스에서는 어떤 세 원소를 고르더라도 조건을 만족하므로 $C(10^6, 3)$의 결과와 같다는 것도 알 수 있다.