[자바] 백준 2517 - 달리기 (java)

 문제 : boj2517

---

 

필요 알고리즘 개념

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

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

 

---

 

풀이

  자신보다 실력이 좋은 사람은 이길 수 없다는 조건이므로, 배열의 각 위치에서 이전에 나온 자신보다 더 큰 값의 수 + 1이 최선의 등수이다. 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15일 때를 생각해보자. ans는 자신보다 idx가 작은 위치에서 자신보다 arr[idx]의 값이 더 큰 수 + 1로, 최선의 등수를 뜻한다. 이하 idx 0부터 7까지의 ans를 구하는 과정이다.

 

 

 

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

 

 

  다만 이 문제에서 값은 최대 10억이라서, 펜윅이나 세그먼트 트리를 사용할 시 구간의 범위가 너무 넓다. 하지만 N은 최대 50만이고, 값에서 중요한건 어떠한 값보다 크거나 작다를 알기만 하면 될 뿐이지 값 자체가 중요한건 아니다. 즉, 실력이 각각 '50000 123 36434455' 이었다면, '2 1 3' 으로 변경하더라도 서로 실력의 크고 작은 것만 바뀌지 않는다면 전혀 상관이 없다.

 

 

  따라서 값을 압축해서 사용하자.(코드의 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;

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 int getAnswer(int i) {
        int 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;
        for (int i = 1; i <= n; i++) {
            arr[i] = compArr[i] = Integer.parseInt(br.readLine());
        }

        valueCompression(compArr);
        setCompressionValueToArr(arr);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(getAnswer(arr[i]-1)+1).append('\n');
            update(arr[i]);
        }
        System.out.print(sb);
    }

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