이전에도 비슷한 문제가 있었던것 같은데.
Inversion Count 수 구하기...
Swap의 개수를 구하는 문제와 동일한 형태로.
기본 코드는 아래와 같다.
static int getInversionCnt(int[] A, int n) {
int inv_cnt = 0;
for(int i=0; i<n-1 ; i++){
for(int j=i+1 ; j<n ; j++) {
if(A[i] > A[j] {
inv_cnt++;
}
}
}
return inv_cnt;
}
위 코드는 기본 Sorting 시 숫자를 세는 거고, 변경 위치를 세는 경우, 다른 방식을 사용해야 함.
관련 문제가 백준에 있어 링크한다.
https://www.acmicpc.net/problem/7578
7578번: 공장
어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블로 연결되어 있다. 즉, A열의 임의의 기계는 B열의 유일한 기계와 케이블로 연결되어 있고, B열의 임의의 기계는 A열의 유일한 기계와 케이블로 연결되어 있다 또한, 각 기계에는 식별번호가 붙어있으며, 짝이 맺어진 기계끼리는 같은 식별번호가 붙어있다. 즉,
www.acmicpc.net
케이블의 교차수를 세는 문제지만, 펜윅트리(BIT) 혹은 세그먼트 트리로 풀수 있음.
교차점에 따른 모든점을 계산할 필요 없이, 앞에서 부터 이동하는 위치의 거리만 계산해주면 됨.
문제를 푸는 방법은
1. 펜윅트리를 만든다. 초기값은 모두 0
2. 1~n까지 탐색을하며 B에서의 나의 위치 뒤에있는 것의 합을 더한다!
3. 그리고 나의 위치를 트리에서 1로 바꿔준다
교차점의 수를 세는 것이므로 A의 앞에있던 공장이 B에서는 뒤에있다면 교차점이 생긴다. 그래서 뒤에 1이 몇개있는지만 세어주면 된다!
눈뜬 장님이었네..ㅠㅠ
import java.io.*;
import java.util.StringTokenizer;
public class Factory {
static int N;
static int[] P, NE;
static int[] PT;
static void update(int h, int v, int[] PT) {
for (int i = h; i <= N ; i+=(i&-i)) PT[i] += v;
}
static long query(int h, int[] PT) {
long result = 0;
for (int i = h; i > 0 ; i-=(i&-i)) result += PT[i];
return result;
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/factory_input.txt"));
long Start = System.currentTimeMillis();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st1, st2;
int T = Integer.parseInt(br.readLine().trim());
for (int t = 1; t <= T ; t++) {
N = Integer.parseInt(br.readLine().trim());
P = new int[N+1];
NE = new int[200001];
PT = new int[N+1];
st1 = new StringTokenizer(br.readLine().trim(), " ");
st2 = new StringTokenizer(br.readLine().trim(), " ");
for (int i = 1; i <= N ; i++) {
P[i] = Integer.parseInt(st1.nextToken());
NE[Integer.parseInt(st2.nextToken())] = i;
}
long result = 0;
for (int i = 1; i <= N ; i++) {
result += query(N, PT) - query(NE[P[i]], PT);
update(NE[P[i]], 1, PT);
}
System.out.println("#"+t+" "+result);
}
System.out.println("Total : " + (System.currentTimeMillis()-Start) + " ms");
}
}