백준 북서풍(5419)

북서풍

1. 힌트

1) 섬 $a, b$가 존재하고 $a$에서 $b$로 항해가 가능하다고 하면 $(a, b)$는 조건을 만족하는 하나의 쌍이 되고 이는 $(b, a)$와 같다.

2) $(a, b)$와 같은 쌍을 중복적으로 세지 않기 위해 탐색 순서를 강제한다. $x$좌표를 오름차순으로 순회하면서 $x$가 같다면 $y$좌표의 내림차순으로 순회한다.

3) 구간 합 세그먼트 트리를 통해서 지금까지 고른 $y$좌표들 중 현재 좌표보다 큰 좌표의 개수만큼 추가하면서 모두 세준다.

2. 접근

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

순회 순서를 $x$좌표의 오름차순, $x$좌표가 같다면 $y$의 내림차순으로 하면 임의의 $(x, y)$를 확인할 때, 이전에 고른 좌표들의 $x$값들은 현재 $(x, y)$보다 작거나 같기 때문에 일단 $x$좌표는 조건을 만족한다. 이 중에서 $y$좌표 또한 $(x, y)$보다 큰 경우만 세주면 모든 경우의 수를 셀 수 있다.
구간 합 세그먼트 트리로 update하면서 세준다. 좌표의 범위가 넓지만 좌표의 개수는 $N$개이므로 좌표압축을 적용한다.

3. 구현

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		while (TC-- > 0) {
			int N = Integer.parseInt(br.readLine());
			ArrayList<Pair> S = new ArrayList<>(N); 
			ArrayList<Integer> yLoc = new ArrayList<>(N); 
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");				
				S.add(new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
				yLoc.add(S.get(i).y);
			}
			Collections.sort(S);
			// 좌표 압축
			Collections.sort(yLoc);
			Map<Integer, Integer> compress = new HashMap<>();
			int index = 1;
			for (int y : yLoc) if (compress.get(y) == null) compress.put(y, index++);
			FenwickTree t = new FenwickTree(index - 1);
			long cnt = 0; int n = 0;
			for (Pair p : S) {
				p.y = compress.get(p.y);
				cnt += n - t.sum(p.y - 1);
				t.add(p.y, 1);
				n++;
			}
			bw.append(cnt).append("\n");
		}
		System.out.print(bw);
	}
	
}

class Pair implements Comparable<Pair> {
	int x, y;
	Pair(int x, int y) { this.x = x; this.y = y; }
	
	public int compareTo(Pair o) { return x == o.x ? o.y - y : x - o.x; }
	
}

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) 테스트 케이스