[백준] 2517: 달리기 - JAVA

in Algorithm on 자료 구조

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

풀이

N명의 선수의 실력을 입력받는다. 입력을 받는 순서대로 해당 위치에 있다고 할 때,

실력이 자기보다 안좋은 선수가 앞에 있으면 역전할 수 있다.

예를들어 실력이 2, 8, 10으로 주어졌다면 8실력을 가진 선수는 앞에 자기보다 낮은 실력의 선수 1명이 있으므로 이 선수가 할 수 있는 최선의 등수는 1등이다.

10인 선수는 앞에 2명을 앞지를 수 있으므로 최선의 등수는 1등이 된다.

세그먼트 트리를 이용하여 실력을 tree의 인덱스로 하여 1늘린다.

1부터 자신의 인덱스까지 구간합을 구하면 자신과 자신보다 실력이 낮은 선수들의 합이 된다.

구간합과 입력받은 순서를 이용하여 최선의 등수를 계산할 수 있다.

각 선수의 실력은 모두 다르므로 주어진 실력을 압축하여 1~N의 숫자로 실력을 저장했다.

메모리: 101924KB

시간: 1932ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {
    static class SegmentTree {
        long[] tree;

        public SegmentTree(int arrSize) {
            tree = new long[arrSize * 4];
        }

        public void update(int node, int start, int end, int idx) {
            if (idx < start || end < idx) {
                return;
            }

            tree[node] += 1;

            if (start != end) {
                update(node * 2, start, (start + end) / 2, idx);
                update(node * 2 + 1, (start + end) / 2 + 1, end, idx);
            }
        }

        public long sum(int node, int start, int end, int left, int right) {
            if (left > end || right < start) {
                return 0;
            }

            if (left <= start && end <= right) {
                return tree[node];
            }

            return sum(node * 2, start, (start + end) / 2, left, right)
                    + sum(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
        }
    }

    static class Node {
        int idx;
        int skill;

        public Node(int idx, int skill) {
            this.idx = idx;
            this.skill = skill;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        List<Node> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());
            list.add(new Node(i, x));
        }
        Collections.sort(list, (a, b) -> (a.skill - b.skill));
        for (int i = 0; i < N; i++) {
            list.get(i).skill = i + 1;
        }
        Collections.sort(list, (a, b) -> (a.idx - b.idx));

        SegmentTree seg = new SegmentTree(N);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int x = list.get(i).skill;
            seg.update(1, 1, N, x);

            long result = i - seg.sum(1, 1, N, 1, x) + 2;
            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }

}