백준 10090 자바 - Counting Inversions (boj 10090 java)

문제 : boj10090

 

 

  n개를 입력받으면서 매번 입력받은 값이 k라 하면, 매번 이전까지 나온 수 중 k보다 큰 수가 몇 번 나왔는지만 알면 된다. 머지소트트리, 세그먼트트리, 제곱근 분할법이 이걸 알 수 있는 자료구조들이다(물론 더 있을 수 있다). 별다른 응용없이 해당 자료구조 중 아무꺼나 적용하면 풀리는 문제라 셋 중 맘에 드는걸로 검색해서 배워보자! 개인적으로 구현 난이도는 제곱근 분할법 < 머지소트트리 << 세그먼트트리 이다. 시간 복잡도는 내가 알기론 그 역순이다(어려우면 빨라야지!).

  

  이하 코드는 제곱근 분할법으로 구현한 코드이다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int n, sqrtN;
    int[] bucket, cnt;

    private void add(int num) {
        cnt[num]++;
        bucket[num/sqrtN]++;
    }

    private int getAnswer(int num) {
        int totalCnt = 0;
        while (num%sqrtN != 0 && num!=n+1)
            totalCnt += cnt[num++];
        if (num != n+1) {
            for (int i = num/sqrtN; i < bucket.length; i++) {
                totalCnt += bucket[i];
            }
        }
        return totalCnt;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        sqrtN = Math.max(1, (int)Math.sqrt(n));
        bucket = new int[n/sqrtN+1];
        cnt = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        long answer = 0;
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            answer += getAnswer(num);
            add(num);
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}