[BOJ] 2517 달리기 - Java

[원문링크]

https://adorable-aspen-d23.notion.site/BOJ-2517-3bfb4962163f45d190eb99a4fc962f72

[BOJ] 2517

 

[풀이]

• 조건 : 나보다 index가 작은 애들 중에 나보다 실력이 안좋은 애들 수
• 인덱스 트리
  • 담는 순서 : 실력이 안좋은 애들 순으로 넣기
  • index : 애들 index 그대로
  • value : 나보다 index가 작으면서 실력이 안좋은 애들 수
• 실력이 안좋은 애들부터 담으니까 그 앞에 몇개가 존재하는지를 찾으면 정답을 알 수 있다.

[코드]

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

public class Boj2517_달리기 {
    static int N;
    static int[] indexTree;
    static Player[] player;
    static int treeSize, offset; //leaf노드 바로 전 index
    static int[] answer;

    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        treeSize = getTreeSize();
        indexTree = new int[treeSize];
        player = new Player[N+1];
        answer = new int[N+1];
        offset = (treeSize >> 1) - 1; //treeSize/2 - 1

        player[0] = new Player(0,0);
        for(int i=1;i<N+1;i++){
            player[i] = new Player(i,Integer.parseInt(br.readLine()));
        }

        Arrays.sort(player); //실력 안좋은 순으로 정렬

        for(int i=1;i<N+1;i++){
            //query(1,index) 진행하면 앞지를 수 있는 수 나옴
            int subValue = query(1,N,1,1,player[i].idx);
            answer[player[i].idx] = player[i].idx - subValue;

            //update 진행
            updateTree(1,N,1, player[i].idx,1);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=1;i<N+1;i++){
            sb.append(answer[i]).append("\\n");
        }
        System.out.println(sb);
    }

    static int query(int start, int end, int index, int targetStart, int targetEnd){
        if(targetEnd < start || targetStart > end){
            return 0;
        }
        if(targetStart <= start && end <= targetEnd){
            return indexTree[index];
        }
        int mid = (start+end)/2;
        return query(start,mid,index*2,targetStart,targetEnd) + query(mid+1,end,index*2+1,targetStart,targetEnd);
    }

    static void updateTree(int start,int end, int index, int target, int diff){
      
        //범위가 아닐 때
        if(start > target || end < target){
            return;
        }
        indexTree[index] += diff;
        //leaf노드면 리턴
        if(start == end){
            return;
        }
        int mid = (start+end)/2;
        updateTree(start,mid,index*2,target,diff);
        updateTree(mid+1,end,index*2+1,target,diff);
        return;
    }

    static int getTreeSize(){
        int k=1; //2^K >= N 찾기
        while(k < N){
            k *= 2;
        }
        return k * 2;
    }

    static class Player implements Comparable<Player>{
        int idx;
        int value;

        public Player(int idx, int value) {
            this.idx = idx;
            this.value = value;
        }

        @Override
        public int compareTo(Player o) {
            return Integer.compare(this.value,o.value);
        }
    }
}

얻어가는 것

• segment tree
• StringBuilder의 중요성
  • System.out.println쓰니까 시간초과 나왔다.
  • 귀찮더라도 StringBuilder 사용 해보기..

StringBuilder sb = new StringBuilder();
sb.append(answer).append("\\n");

//출력
System.out.println(sb);

느낀점

"220201"

소요 시간 : 2h

• segment tree