백준 버블 소트(1517)

버블 소트

1. 힌트

1) $S$에서 가장 작은 원소부터 맨 왼쪽으로 옮기는 식으로 생각하여도 답에는 변함이 없다. $S[i]$가 맨 왼쪽까지 가는데 필요한 비용은 자신보다 왼쪽에 있는 자기보다 큰 원소의 개수이다.

2) 누적 합을 이용하면 자기보다 왼쪽에 있는 원소의 개수를 $O(1)$에 구할 수 있다. 하지만 원소를 실제로 맨 왼쪽으로 옮기게 하면 인덱스가 모두 바뀌어버려서 누적 합을 다시 구해야한다. 가장 작은 원소부터 옮기므로 한번 옮긴 원소는 누적 합에서 제거해버려도 된다. 이렇게하면 인덱스를 바꾸지 않고 구현할 수 있다.

3) 원소에 중복이 있을 수 있다. 같은 값 중에서는 더 앞에있는 값을 먼저 옮긴다.

2. 접근

1) 단순한 방법에서 시작할 수 있을까?

버블 소트는 수열에서 $N$개의 인접한 짝 $(i, i + 1)$들을 비교해보면서 $S[i]$와 $S[i + 1]$을 바꿔주고, 이와 같은 과정을 $N$번 반복하는 $O(N^2)$의 정렬 방법이다. 정렬 과정에서 가장 처음에 $N$번의 인접한 짝을 비교하면서 바꾸고나면 수열의 오른쪽 끝 $S[N]$에는 무조건 최댓값이 위치하게 된다. $0$번째 인덱스부터가 아니라 $S[N]$이 존재하던 위치부터 바꾼다고 생각해보자. $S[N]$이 오른쪽 끝까지 오는데 몇 번의 swap이 일어났을까? $S[i] > S[i + 1]$일때만 swap이 일어나므로 $S[i]$보다 오른쪽에 위치하는 수 중에서 $S[i]$보다 작은 수의 개수만큼 swap이 일어나게 된다.

4) 문제를 단순화할 수 없을까?

$S$의 모든 원소에 대해서 자기보다 오른쪽에 있는 작은 수의 개수를 $O(N)$의 과정으로 일일히 세준다면 $O(N^2)$으로 시간초과를 피할 수 없을 것이다. 우리는 $S$의 원소를 크기가 큰 순서부터 순회한다면 자기보다 오른쪽에 있는 수는 모두 자기 자신보다 작다는 것에서 아이디어를 얻을 수 있다(확인한 후에는 자기 자신을 삭제). 이를 통해서 누적 합을 적용할 수 있다. 하지만 순회 과정중에서 자기 자신을 삭제해야하므로 update연산이 필요하다. 이를 세그먼트 트리르 이용해 구현할 수 있다.
구현을 간단히 하기 위해서 위에서는 $S$의 원소를 크기가 큰 순서로 맨 오른쪽으로 보내줬지만 이를 $S$의 원소를 크기가 작은 순서로 맨 왼쪽으로 보내줘도 문제는 동일하다.

3. 구현

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());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int[] S = new int[N];
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		FenwickTree t = new FenwickTree(N);
		for (int i = 1; i <= N; i++) t.add(i, 1);
		// map[x] = x가 S의 몇번째에 있는지 반환 (1-based), x가 여러개일 수 있으므로 작은 것 부터 
		Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
		for (int i = 0; i < N; i++) {
			PriorityQueue<Integer> pq = map.get(S[i]);
			if (pq == null) map.put(S[i], pq = new PriorityQueue<>());
			pq.offer(i + 1);
		}
		Arrays.sort(S);
		long ret = 0;
		for (int i = 0; i < N; i++) {
			PriorityQueue<Integer> pq = map.get(S[i]);
			while (!pq.isEmpty()) {
				int x = pq.poll();
				ret += t.sum(x) - 1;
				t.add(x, -1);
			}
		}
		System.out.println(ret);
	}
	
}

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

1) 시간 복잡도

2) 테스트 케이스