[자바] 백준 1517 - 버블 소트 (java)

 문제 : boj1517

---

 

필요 알고리즘 개념

•  세그먼트 트리, 펜윅트리 등의 구간 쿼리 알고리즘
  • 이 문제의 경우 분할 정복을 통해서도 풀 수 있는 것으로 알고 있다. 그리고 또다른 정해로 구간 쿼리 알고리즘을 사용해서도 일반적으로 Inversion Counting이라 불리는 기법으로 풀 수 있다.
• 정렬
  
  • 정렬하는 방법을 알아야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  버블 소트의 경우 O(N^2)이 필요하다. 따라서 실제로 버블 소트를 돌려봐서 횟수를 찾으려 한다면 시간초과가 나게된다.

버블 소트는 정렬하려는 배열 arr에서 임의의 인덱스 x가 arr[x-1] > arr[x] 인 경우, arr[x-1]과 arr[x]의 값을 변경하는 방식이다. 즉, arr[x]에서 x-1 이하의 인덱스에 있는 값들 중 arr[x]보다 큰 값은 자신을 지나 더 뒤로 가게 된다. 무슨말이냐면 인덱스 x 위치에 대해, arr[0], arr[2], ... ,arr[x-1] 중 arr[x]보다 큰 값이 들어있는 갯수만큼 버블 소트 교환횟수가 발생한다. 

 

---

 

  따라서 정렬되지 않은 배열 자체에서 순서대로 살펴보면서, 그 이전에 자신보다 더 큰 수가 나온 횟수를 모두 세주면 버블소트 횟수가 된다. 예를들어 다음의 예시를 보자.

5
3 2 3 2 1

 

1. 0번 인덱스는 자신보다 더 이전 값이 없으므로 따로 안세줘도 된다.

 

 

2. 1번 인덱스에 대해서는 arr[1]=2이므로, 그보다 큰 값은 arr[0]의 1개이다.

 

3. 2번 인덱스에 대해서는 이전에 더 큰 값이 없다.

 

4. 3번 인덱스에 대해서는 더 큰 값이 이전에 2개가 있다.

 

5.  4번 인덱스보다 더 큰 값은 이전에 4개가 있다. 최종적으로 1 + 2 + 4 = 7개가 답이 된다.

 

---

  근데 가만히 생각해보면, N개의 인덱스에 대해 이전 모든 값을 살펴보니까 결국 O(N^2)이 되니 통과가 못할것임을 알 수 있다. 이걸 줄이기 위해 세그먼트 트리 혹은 펜윅 트리를 사용하자. 일반적으로 사용하는 것 처럼 배열의 인덱스에 대한 구간으로 생각하지 말고, 존재하는 값에 대한 구간으로 생각해보자. 만약 arr[x]가 3이라면, 펜윅이나 세그먼트 트리를 통해 [3+1, 최대값] 의 구간에 대해 등장한 횟수를 계산하는 방식이다. 이런식으로 한다면 O(NlogN)이 되므로 통과할 수 있다.

 

  다만 이 문제에서 값의 범위는 '-10억 ~ 10억'이라서, 펜윅이나 세그먼트 트리를 사용할 시 구간의 범위가 너무 넓다. 하지만 N은 최대 50만이고, 값에서 중요한건 어떠한 값보다 크거나 작다를 알기만 하면 될 뿐이지 값 자체가 중요한건 아니다. 즉, 아래와 같은 예시를 생각해보자. 

3
-1000000000 999999999 42312

이 때 위 값을 그대로 쓰는 것과, -1000000000 -> 1, 42312 -> 2, 999999999 -> 3으로 변경하여 아래와 같이 사용하는 것은 로직에 아무런 영향이 없다.

3
1 3 2

 

  따라서 값을 압축해서 사용하자.(코드의 valueCompression())

이하 코드는 펜윅트리를 사용한 코드로, 펜윅 트리 글에서 '기본' 부분을 보면 풀 수 있다. 내 경우엔 추가로 펜윅 트리에서는 [A, N]  구간에 대해 쿼리를 하게되면 [1, N]과 [1, A-1]의 두가지 쿼리를 해줘야 한다. 하지만, 압축할 때 역으로 큰 값을 작은값으로 압축해주게 되면 이 문제는 '이전에 나온 자신보다 작은 값'을 찾는것으로 변경이 되고, 그렇다면 [1, A] 쿼리 하나 만으로 처리가 가능해지므로 역순으로 압축을 해줬다. 

 

  

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    int n;
    int[] arr, bit;
    HashMap<Integer, Integer> mapping = new HashMap<>();

    private void valueCompression(Integer[] compArr) {
        Arrays.sort(compArr, Comparator.reverseOrder());

        int comp = 1;
        int bf = compArr[0];
        for (int i = 1; i <= n; i++) {
            if (compArr[i] == bf) {
                continue;
            }
            bf = compArr[i];
            mapping.put(compArr[i], comp++);
        }
    }

    private void setCompressionValueToArr(int[] arr) {
        for (int i = 1; i <= n; i++) {
            arr[i] = mapping.get(arr[i]);
        }
    }

    private long getAnswer(int i) {
        long sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i&-i;
        }
        return sum;
    }

    private void update(int i) {
        while (i <= n) {
            bit[i]++;
            i += i&-i;
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        bit = new int[n+1];
        Integer[] compArr = new Integer[n+1];
        compArr[0] = 1000000001;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = compArr[i] = Integer.parseInt(st.nextToken());
        }

        valueCompression(compArr);
        setCompressionValueToArr(arr);

        long answer = 0;
        for (int i = 1; i <= n; i++) {
            answer += getAnswer(arr[i]-1);
            update(arr[i]);
        }
        System.out.println(answer);
    }

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