[백준문제풀이] 2517 달리기 java

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

2517번: 달리기

접근법 : 

**1) 어떻게 풀 것인가?**

알고리즘수업을들으면서 풀게 된 문제 중 하나이다. 

그냥 단순하게 이 문제를 생각하면, 인덱스 순서대로 값이 더 큰 값의 개수를 구하면 된다.

근데 이런식으로 풀게되면 시간복잡도가 N^2가 되어버리고, 이는 시간복잡도 1초를 못지키게 되어 다른 방법을 생각해야한다. 

이 문제는 인덱스트리에 대해서 배웠을때 풀어보았던 문제로, 강사님께서 인덱스트리로 풀어보라고 힌트도 주셔서 

인덱스트리 + 구간합 문제로 풀 수 있었다. 

 

**2) 시간복잡도**

인덱스드트리 값 수정 : logN

인덱스드트리 구간 합 구하기 : N* logN 

으로 logN을 두번 수행하므로, 이는 N* 2* logN = 약 2 * 10^7 정도...된다.

 

**3) 공간복잡도**

256mb

 

**4) 풀면서 놓쳤던점**

값을 어떻게 저장할지에 대해서 생각을 못했는데, 

value[]에서 인덱스를 활용하여 값을 저장하는 방법을 알게되었다. 

 

**5) 이 문제를 통해 얻어갈 것**

인덱스트리

구간합

그리고 이 문제는 나에게 1.참신한 문제 2. 인덱스드트리를 잘 이해시켜준 문제로, 굉장히 중요하다!

 

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

public class Main {
    static class runner implements Comparable<runner> {
        int rank;
        int speed;
        public runner(int rank, int speed){
            this.rank = rank;
            this.speed =speed;
        }
        //내림차순. 15 10 9 ...
        @Override
        public int compareTo(runner r) {
            return r.speed-this.speed;
        }
    }
    static int n,offset;
    static int[] value; //최종 값
    static runner[] runners;
    static int[] idxtree;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        runners = new runner[n];
        value = new int[n];
        for(int i=0;i<n;i++){
            runners[i] = new runner(i,Integer.parseInt(br.readLine()));
        }
        for(offset=1;offset<n;offset*=2);
        idxtree = new int[offset*2+2];
        Arrays.sort(runners);//내림차순 정렬 완
        for(int i=0;i<n;i++){
            runner r = runners[i];
            getTree(r);
        }
        for(int i=0; i<n;i++){
            sb.append(value[i]).append("\n");
        }
        System.out.println(sb);
    }
    public static void getTree(runner r){
        int idx = r.rank+offset;
        idxtree[idx] = 1;
        int a  = idx;
        while(a>=1){
            a /= 2;
            idxtree[a] = idxtree[a*2]+idxtree[a*2+1];
        }
        getRank(idx);
    }
    public static void getRank(int idx){
        int l = offset;
        int r = idx;
        int answer =0;
        while(l<=r){
            //홀수
            if((l&1)== 1){
                answer += idxtree[l++];
            }
            //짝수
            if((r&1) == 0){
                answer += idxtree[r--];
            }
            l /= 2;
            r /= 2;
        }
        value[idx-offset] = answer;
    }
}