[Java] 백준 2517 달리기

문제

https://www.acmicpc.net/problem/2517

2517번: 달리기

 

풀이

현재 위치 i 에서 0..i-1 중에 자신의 실력보다 낮은 개수를 센 다음, 차를 구하는 문제.

 분할 정복으로 정렬해서 O(N log N) 풀이하였다. 

 알고리즘은 다음과 같다.

 

1. 분할 정복 소트 기법을 사용한다.
2. 두 배열을 병합할때 RIght 배열 원소를 삽입 할때 자기 Left 배열에서 현재숫자보다 낮은 개수를 누적합한다.
3. 자기 자신의 인덱스 - 자신 실력보다 낮은 선수의 숫자 + 1 을 정답 배열에 담는다.

분할 정복이 처음이신 분들은 백준 예제에, 위 알고리즘을 적용한 풀이 사진을 참고하길 바란다.

주황색 동그라미가 자기보다 왼쪽 숫자 중에서, 자신보다 작은 개수 누적합 부분이다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Data {
    public int num, idx, low;
    Data(int num, int idx, int big){
        this.num = num;
        this.idx = idx;
        this.low = big;
    }
}
class Main {
    Data[] a, b;

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        int ans[] = T.solution(arr);
        for(int i = 0 ;i < n ;i++){
            ans[i] = i - ans[i] + 1;
        }
        StringBuilder sb = new StringBuilder();
        for(int x : ans)
            sb.append(x).append("\n");
        System.out.println(sb.toString());
    }

    public int[] solution(int[] nums) {
        int n = nums.length;
        a = new Data[n];
        b = new Data[n];
        for (int i = 0; i < n; i++) {
            a[i] = new Data(nums[i], i, 0);
        }
        devide(0, n - 1);
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            answer[a[i].idx] = a[i].low;
        }
        return answer;
    }

    public void devide(int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            devide(left, mid);
            devide(mid + 1, right);
            int p1 = left;
            int p2 = mid + 1;
            int p3 = left;
            while (p1 < mid + 1 && p2 < right + 1) {
                if (a[p1].num > a[p2].num) {
                    b[p3] = a[p2++];
                    b[p3++].low += (p1 - left);
                } else {
                    b[p3++] = a[p1++];
                }
            }
            while (p2 < right + 1) {
                b[p3] = a[p2++];
                b[p3++].low += (p1 - left);
            }
            while (p1 < mid + 1) b[p3++] = a[p1++];

            for (int i = left; i < right + 1; i++) {
                a[i] = b[i];//update sorted data
            }
        }

    }
}