[백준/BOJ] 백준 2336번 : 굉장한 학생

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

2336번: 굉장한 학생

 

세그먼트 트리를 이용하여 세 가지 성적(성적 1, 성적 2, 성적 3)을 비교하는 방법으로 문제를 해결했다. 이때 세그먼트 트리는 세그먼트 트리의 [성적 2 등수를 나타내는 위치] = (성적 3의 등수)를 저장해서 활용했다.

 

각각의 학생마다 세 가지 성적의 등수를 저장하고, 성적 1 등수를 기준으로 정렬하면 확인하는 학생보다 앞에 있는 학생들은 해당 학생보다 성적 1이 좋다는 뜻이므로 앞에 있는 학생들 중 성적 2와 성적 3이 좋은 학생이 있는지 찾으면 된다.

 

성적 1이 앞선 학생들 중 성적 2도 더 좋은 학생들을 찾는 방법은 세그먼트 트리 범위 [0~해당 학생의 성적 2 등수-1]의 최소 쿼리 결과에 이미 저장된 값이 있으면 그 자체로 성적 1이 좋은 학생들 중에 성적 2가 좋은 학생이 존재한다는 뜻이다(해당 학생보다 성적 1이 좋은 학생은 성적 2가 이미 먼저 저장되었으므로)

 

그리고 해당 학생보다 성적 1, 성적 2가 좋은 학생 중 성적 3이 좋은 학생은 위의 쿼리 결과가 해당 학생의 성적 3 등수보다 작게 되면 해당 학생 보다 성적 1, 성적 2, 성적 3이 좋은 학생이 존재한다는 점을 이용하여 문제를 해결했다.

 

확인한 학생의 성적2와 성적 3은 세그먼트 트리의 [성적 2를 나타내는 위치] = (성적 3의 등수)로 저장하는 업데이트를 실행했다.

 

코드

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

struct info {
	int rank1;
	int rank2;
	int rank3;
};

//성적1이 더 좋은것 순으로 정렬
bool cmp(info& a, info& b)
{
	if (a.rank1 < b.rank1)
		return true;
	return false;
}

int n;
vector<info> rank_info(500001); //[학생번호] = 해당 학생의 성적
vector<int> sgmtt(500001 * 4, 987654321);
int result = 0;

int UpdateSgmtt(int here, int range_left, int range_right, int index, int value)
{
	if (range_left == range_right && range_right == index)
		return sgmtt[here] = value;
	if (index < range_left || range_right < index)
		return sgmtt[here];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return sgmtt[here] = min(UpdateSgmtt(left_child, range_left, range_mid, index, value), UpdateSgmtt(right_child, range_mid + 1, range_right, index, value));
}

int QuerySgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_left <= range_left && range_right <= find_right)
		return sgmtt[here];
	if (find_right < range_left || range_right < find_left)
		return 987654321;

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return min(QuerySgmtt(left_child, range_left, range_mid, find_left, find_right), QuerySgmtt(right_child, range_mid + 1, range_right, find_left, find_right));
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 1; i <= 3; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input; //i시험에서 j등인 학생의 번호는 input

			if (i == 1)
				rank_info[input].rank1 = j;

			else if (i == 2)
				rank_info[input].rank2 = j;

			else
				rank_info[input].rank3 = j;
		}
	}

	//성적1이 좋은 순서대로 정렬
	sort(rank_info.begin() + 1, rank_info.begin() + n + 1, cmp);

	for (int i = 1; i <= n; i++)
	{
		int this_rank1 = rank_info[i].rank1;
		int this_rank2 = rank_info[i].rank2;
		int this_rank3 = rank_info[i].rank3;

		//해당 학생보다 성적1이 좋은 학생중에서 성적2, 성적3이 좋은 학생이 있는지 찾는다
		//우선 해당 학생보다 먼저 저장된 학생은 해당 학생보다 성적 1이 좋다는 뜻
		//쿼리의 값이 987654321이 아니라는것 만으로도 해당학생보다 성적1이 좋은학생 중에 성적2가 좋은 학생이 있다는 뜻이고
		//게다가 그 쿼리의 값이 this_rank3보다 작으면 성적1,성적2가 좋은 학생중에 성적3이 좋은 학생이 있다는 뜻이다
		if (QuerySgmtt(0, 0, n, 0, this_rank2 - 1) > this_rank3)
			result++;

		//this_rank2의 위치에 this_rank3의 성적을 저장한다
		UpdateSgmtt(0, 0, n, this_rank2, this_rank3);
	}

	cout << result << "\n";

	return 0;
}