(백준) 달리기_2517

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

 

🐢 설명

자신보다 느린 사람이 앞에 있다면 모두 추월할 수 있다는 가정하에 최대 몇등을 기대할 수 있는지 계산하면 되는 문제이다. 세그먼트 트리를 이용해서 풀 수 있다.

 

<기존 달리고 있는 순서>

능력 : 2, 8, 10, 7, 1, 9, 4, 15

순서 : 1, 2,  3,  4, 5, 6, 7,  8

 

<능력순>

능력 : 15, 10, 9, 8, 7, 4, 2, 1

순서 :  8,  3,  6, 2, 4, 7, 1, 5

 

1. 먼저 현재 달리고 있는 사람들의 순서 + 능력을 기록한다.

2. 이들 각각은 자신의 앞에 있는 자신보다 능력이 높은 사람의 수 + 1 등이 최대 기대 등수 임을 알 수 있다.

3. 위 정보를 가지고 능력순으로 정렬한다. (능력값이 클수록 능력이 좋다) 이 배열을 능력순배열이라고 하자.

4.1~N번 능력순 배열에 접근해서 해당 인덱스에 있는 사람의 인덱스를 확인하고 그 인덱스를 가지고 기대 되는 등수 배열에 Q(1, 구한 인덱스)를 통해 앞에 존재하는 인원수를 구하고, 인원수 + 1을 기록한다.

 

즉, 능력 순으로 접근하므로 자신의 앞에 기록된 사람 수는 절대로 추월을 못함을 알고 있으므로 1~자신의 인덱스 사이의 모든 사람 수 + 1이 자신의 등수가 된다. 또한 능력이 떨어지는 사람도 1번에서 달리고 있다면 앞에 사람이 없으므로 1등이 예상된다. 따라서 1~1사이의 사람수를 세면 0이 되어 1등을 할것이라 예상하게 된다.

 

예제를 참고해 보면 1 ~ N명의 사람들에 대해 인덱스를 가지고 능력순배열에 접근한다. 능력순배열[1]에 담긴 사람의 인덱스를 확인한다. 가장 능력이 좋은 15 능력을 가진 8번이 1번에 있을 것이므로 8이 반환된다. 그럼 1~8번 사이의 사람 수를 세고, 그 수 + 1을 등수로 기록한다. 사람수 배열에는 1을 추가해준다.

 

🐢코드

package 인덱스트리;

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

public class 달리기_2517 {
	static int N;
	static int S;
	static Runner[] runnersSkillOrder;
	static int[] tree;
	static int[] runnerResult;
	static StringBuilder answer = new StringBuilder();

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

		N = Integer.parseInt(br.readLine());
		runnersSkillOrder = new Runner[N + 1];
		runnerResult = new int[N + 1];
		S = 1;
		while (S < N) S *= 2;
		tree = new int[S * 2];

		runnersSkillOrder[0] = new Runner(0, 1111111111);
		for (int i = 1; i < N + 1; i++) {
			int skill = Integer.parseInt(br.readLine());
			runnersSkillOrder[i] = new Runner(i, skill);
		}
		Arrays.sort(runnersSkillOrder, Comparator.comparingInt(R -> -R.skill));

		segmentTree();

		for (int order = 1; order < N + 1; order++) {
			answer.append(runnerResult[order]).append("\n");
		}
        
		System.out.print(answer);
	}

	private static void segmentTree() {
		for (int i = 1; i < N + 1; i++) {

			int runnerOrder = i;
			Runner runner = runnersSkillOrder[runnerOrder];

			if (runner.order == runnerOrder) {
				int count = query(1, 1, S, 1, runnerOrder);
				runnerResult[runnerOrder] = count + 1;
			} else {
				runnerOrder = runner.order;
				int count = query(1, 1, S, 1, runnerOrder);
				runnerResult[runnerOrder] = count + 1;
			}

			update(runnerOrder);
		}
	}

	private static void update(int node) {
		int cur = S + node - 1;

		while (cur >= 1) {
			tree[cur] += 1;
			cur /= 2;
		}
	}

	private static int query(int node, int start, int end, int queryLeft, int queryRight) {
		if (start > queryRight || end < queryLeft) return 0;

		if (start == end) return tree[node];

		if (queryLeft <= start && end <= queryRight) return tree[node];

		int mid = (start + end) / 2;
		return query(node * 2, start, mid, queryLeft, queryRight) +
				query(node * 2 + 1, mid + 1, end, queryLeft, queryRight);
	}

	private static class Runner{
		int order;
		int skill;

		public Runner(int order, int skill) {
			this.order = order;
			this.skill = skill;
		}
	}
}

🐢 마무리