[백준 2517] 달리기

1. 문제 

 

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

2517번: 달리기

---

2. 풀이

 

세그먼트 트리를 이용한 문제이다. 물론 나는 인덱스 트리로 풀었다. 인덱스 트리에 대해 잘 모른다면 먼저 공부하고 오자!

인덱스 트리 : https://kinngife.tistory.com/32

인덱스 트리 (Binary Indexed Tree)

 

N명의 달리기 실력이 현재 등수 순서대로 주어졌을 때, 각 선수의 최선의 등수를 구하는 문제이다. 최선의 등수를 구하는 것이므로 현재 등수 또한 매우 중요하다. 나보다 달리기 실력이 좋은 선수가 있다고 하더라도 현재 등수가 자기보다 낮다면 그 선수는 무시할 수 있기 때문이다. 또한, 내가 현재 등수가 낮더라도 달리기 실력이 좋다면 1등을 할 수 있다. 

 

예제에서 8명의 선수의 달리기 실력이 다음과 같이 주어졌다. 

1번 선수 : 2

2번 선수 : 8

3번 선수 : 10

4번 선수 : 7

5번 선수 : 1

6번 선수 : 9

7번 선수 : 4

8번 선수 : 15

 

1번 선수부터 차례로 최선의 등수를 생각해 보자. 

1번 선수 : 아무한테도 추월당하지 않고 1등을 할 수 있다. 

2번 선수 : 1번 선수를 추월하고 1등을 할 수 있다. 

3번 선수 : 1, 2번 선수를 모두 추월하고 1등을 할 수 있다. 

4번 선수 : 2, 3번 선수는 추월하지 못하지만 1번 선수를 추월하고 3등을 할 수 있다. 

5번 선수 : 아무도 추월하지 못하므로 5등이다. 

6번 선수 : 3번 선수를 제외하고 모두 추월할 수 있으므로 2등을 할 수 있다. 

7번 선수 : 1번과 5번 선수만 추월할 수 있으므로 5등을 할 수 있다. 

8번 선수 : 모든 선수를 추월할 수 있으므로 1등을 할 수 있다. 

 

 

위에서 적은 것을 토대로 규칙을 파악할 수 있다. 바로 달리기 실력에 따라 내 앞에 있는 선수들 중에서 추월할 수 있는 선수들을 모두 추월한 상태가 바로 최선의 등수인 것이다. 따라서 추월하지 못한 선수가 몇 명인지 즉, 내가 추월할 수 있는 선수를 모두 추월했을 때 내 앞에 존재하는 선수들의 합에 1을 더한 값이 내 등수이다. 왜냐하면 내 앞에 3명이 있다고 했을 때 나의 등수는 3에다가 1을 더한 4등이 되기 때문이다. 

 

내 앞에 존재하는 선수들의 합? 바로 구간 합을 구하는 문제다. 바로 세그먼트 트리 or 인덱스 트리를 떠올려야 한다!

근데 입력값의 범위를 잘 살펴볼 필요가 있다. N은 최대 50만이지만 달리기 실력의 범위는 1부터 10억이다. 달리기 실력의 범위가 크지 않았다면 단순하게 달리기 실력으로 인덱스 트리를 만들어 구간 합을 구하면 됐을 것이다. 하지만 달리기 실력의 범위가 매우 크므로 인덱스 트리를 적용할 수 없다. 그러면 N에 대해서 구간 합을 생각해봐야 하는데 어떻게 해야 할까? 나는 생각하는 데 조금 오래 걸렸지만 생각보다 단순하다. 바로 현재 등수를 기억한 상태에서 달리기 실력이 좋은 순서대로 인덱스 트리에 값을 update 하여 구간 합을 구하는 방식이다. 

 

 

예제를 다시 한번 보자. 

1번 선수 : 2

2번 선수 : 8

3번 선수 : 10

4번 선수 : 7

5번 선수 : 1

6번 선수 : 9

7번 선수 : 4

8번 선수 : 15

 

선수마다 달리기 실력과 현재 등수를 pair<int,int>형으로 저장하면 다음과 같다. 

1번 선수 : (2, 1)

2번 선수 : (8, 2)

3번 선수 : (10, 3)

4번 선수 : (7, 4)

5번 선수 : (1, 5)

6번 선수 : (9, 6)

7번 선수 : (4, 7)

8번 선수 : (15, 8)

 

이 상태에서 달리기 실력이 좋은 순서대로 정렬하면 다음과 같다. 

8번 선수 : (15, 8)

3번 선수 : (10, 3)

6번 선수 : (9, 6)

2번 선수 : (8, 2)

4번 선수 : (7, 4)

7번 선수 : (4, 7)

1번 선수 : (2, 1)

5번 선수 : (1, 5)

 

 

이렇게 정렬을 한 상태에서 달리기 실력이 좋은 순서대로 인덱스 트리에서 알맞게 구간 합과 update가 이루어져야 한다. 현재 등수가 자신보다 앞선 선수 중에 자신보다 달리기 실력이 좋은 선수를 구간 합으로 구한 후, 현재 등수에 자신이 존재한다는 의미로 인덱스 트리에 update 해야 한다. 아래와 같이 차례대로 update가 이루어진다. 

 

8번 선수 : 1~7번 선수 중 자신보다 달리기 실력이 좋은 선수는 존재하지 않는다 : 0명 => 1등 & 8번째 index update

3번 선수 : 1~2번 선수 중 자신보다 달리기 실력이 좋은 선수는 존재하지 않는다 : 0명 => 1등 & 3번째 index update

6번 선수 : 1~5번 선수 중 자신보다 달리기 실력이 좋은 선수는 3번 선수이다 : 1명 => 2등 & 6번째 index update

2번 선수 : 1~1번 선수 중 자신보다 달리기 실력이 좋은 선수는 존재하지 않는다 : 0명 => 1등 & 2번째 index update

4번 선수 : 1~3번 선수 중 자신보다 달리기 실력이 좋은 선수는 2,3번 선수이다 : 2명 => 3등 & 4번째 index update

7번 선수 : 1~6번 선수 중 자신보다 달리기 실력이 좋은 선수는 2,3,4,6번 선수이다 : 4명 => 5등 & 7번째 index update

1번 선수 : 자신보다 앞선 선수는 존재하지 않는다 : 0명 => 1등 & 1번째 index update

5번 선수 : 1~4번 선수 중 자신보다 달리기 실력이 좋은 선수는 1,2,3,4번 선수이다 : 4명 => 5등 & 5번째 index update

 

 

위에서 구한 최선의 등수를 요약하면 다음과 같다. 

1번 선수 : 1등

2번 선수 : 1등

3번 선수 : 1등

4번 선수 : 3등

5번 선수 : 5등

6번 선수 : 2등

7번 선수 : 5등

8번 선수 : 1등

 

원래 순서대로 출력을 하라고 했으므로 이렇게 답을 출력하면 된다!

 

 

구현을 해보자. N이 최대 50만이므로 50만보다 처음으로 크거나 같아지는 2의 제곱수는 524,288이다. 이 값을 $OFFSET$이라고 했을 때, 인덱스 트리를 나타내는 tree 배열은 $OFFSET$ * 2만큼의 크기가 필요하다. 

N명의 선수들의 달리기 실력을 pair<int,int>형 arr 배열에 입력받았다고 하자. pair<int,int>형의 첫 번째 원소에 달리기 실력을 입력 받고, 두 번째 원소에 현재 등수를 저장한다. 입력을 모두 받은 후, 달리기 실력이 좋은 순서대로 정렬한다. 

 

int OFFSET = 524288;
vector<int>tree(OFFSET * 2);
vector<ii>arr(500001);
for (int i = 0; i < N; i++) {
	cin >> arr[i].first;
	arr[i].second = i;
}
sort(arr.rbegin(), arr.rend());

 

 

정렬을 했다면 달리기 실력이 좋은 순서대로 인덱스 트리에 update를 하며 최선의 등수를 구한다. 구간 합을 구하는 query 함수와 update 함수는 다음과 같다. 

 

void update(int idx, int num) {
	idx += OFFSET;
	tree[idx] = num;
	while (idx > 1) {
		idx /= 2;
		tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
	}
}
int query(int left, int right) {
	int ret = 0;
	left += OFFSET, right += OFFSET;
	while (left <= right) {
		if (left % 2 == 1) ret += tree[left++];
		if (right % 2 == 0) ret += tree[right--];
		left /= 2, right /= 2;
	}
	return ret;
}

---

3. 전체 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <climits>
#include <cmath>
#define INF INT_MAX
using namespace std;
using ll = long long;
using ii = pair<int, int>;
int N;
int OFFSET = 524288;
vector<ii>arr(500001);
vector<int>tree(OFFSET * 2);

void update(int idx, int num) {
	idx += OFFSET;
	tree[idx] = num;
	while (idx > 1) {
		idx /= 2;
		tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
	}
}
int query(int left, int right) {
	int ret = 0;
	left += OFFSET, right += OFFSET;
	while (left <= right) {
		if (left % 2 == 1) ret += tree[left++];
		if (right % 2 == 0) ret += tree[right--];
		left /= 2, right /= 2;
	}
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i].first;
		arr[i].second = i;
	}
	sort(arr.rbegin(), arr.rend());

	vector<int>ans(N);
	for (int i = 0; i < N; i++) {
		int idx = arr[i].second;
		ans[idx] = query(0, idx - 1) + 1;
		update(idx, 1);
	}

	for (int i = 0; i < N; i++) cout << ans[i] << "\n";

	return 0;
}