취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2318번 문제인 상사 찾기이다.
문제는 아래 링크를 확인하자.

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

지문을 영어로 읽고 풀었으므로 영어 원문을 기준으로 글을 설명하겠다.

지문을 처음 읽고 "주어진 사원의 부하의 수"와 "주어진 사원보다 키가 더 작거나 같고 급료를 더 적게 받는 사람"이 같을 것이라 오판해 헤맸던 문제이다. 이 둘은 실제로는 다를 수 있음에 유의하자.

키가 큰 순서대로, 같은 키라면 급료를 더 많이 받는 순서대로 직원들을 살펴보면서, 지금까지 살펴본 직원들 중 해당 직원보다 급료가 많은 직원 중 가장 적은 급료를 가진 사람을 찾아 각 직원의 직속상사를 구해낼 수 있다. 글쓴이는 "지금까지 살펴본 직원"의 정보를 저장하기 위해 구간합을 다루는 세그먼트트리 자료구조를 이용하였다.

이러한 직속상사 관계를 이용해 주어진 관계를 트리로 모델링할 수 있고, 이 트리 위에서의 자식방향으로의 탐색을 이용하면 각 직원의 부하의 수를 계산할 수 있다. 이를 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int M, Q;
map<int, int> idtoidx;
int idxtoid[30001];
map<int, int> salarytoidx;
pair<int, int> P[30001]; // {height, salary}

short seg[33554433]; // [L]: 봉급이 L인 사람이 있음

void update(int qI) {
	int L = 1, R = 10000001, sI = 1;
	while (L < R) {
		seg[sI]++;
		int mid = (L + R) / 2;
		if (qI > mid) L = mid + 1, sI = sI * 2 + 1;
		else R = mid, sI = sI * 2;
	}
	seg[sI]++;
}

int nthquery(int nth) {
	int L = 1, R = 10000001, sI = 1;
	while (L < R) {
		if (seg[sI * 2] < nth) {
			nth -= seg[sI * 2];
			L = (L + R) / 2 + 1, sI = sI * 2 + 1;
		}
		else R = (L + R) / 2, sI = sI * 2;
	}

	return L;
}

short rangesum(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return rangesum(L, (L + R) / 2, qL, qR, sI * 2) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

vector<int> G[30001];
int par[30001];

int dfs(int cur) {
	int ret = 1;
	for (auto& nxt : G[cur]) ret += dfs(nxt);

	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> M >> Q;
	for (int idx = 1; idx <= M; idx++) {
		int id, salary, height; cin >> id >> salary >> height;
		idtoidx.insert(make_pair(id, idx));
		idxtoid[idx] = id;
		salarytoidx.insert(make_pair(salary, idx));
		P[idx - 1] = make_pair(height, salary);
	}

	sort(P, P + M);
	update(10000001);

	for (int i = M - 1; i > -1; i--) {
		int idx = salarytoidx[P[i].second];
		update(P[i].second);
		int salaryboss = nthquery(rangesum(1, 10000001, 1, P[i].second, 1) + 1);
		if (salaryboss > 10000000) par[idx] = -1;
		else {
			par[idx] = salarytoidx[salaryboss];
			G[par[idx]].emplace_back(idx);
		}
	}

	while (Q--) {
		int id; cin >> id;
		int idx = idtoidx[id];

		if (par[idx] < 0) cout << 0 << ' ' << dfs(idx) - 1 << '\n';
		else cout << idxtoid[par[idx]] << ' ' << dfs(idx) - 1 << '\n';
	}
}