[백준/BOJ] 백준 2465번 : 줄 세우기

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

2465번: 줄 세우기

 

키 순위에 대해 해당 키 순위의 키가 몇 개 있는지 rank_cnt에 rank_cnt[키 순위] = 해당 키의 개수 형식으로 저장해 놓고 이를 이용한 합 세그먼트 트리 sum_sgmtt를 만든다. 그리고, 수열 s의 마지막번째부터 어떤 순위에 속하는지 이분 탐색을 통한 세그먼트 트리 쿼리를 통해 찾아내는 과정을 통해 문제를 해결했다.

 

코드

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

int n;
vector<int> height;
vector<int> s;
map<int, int> height_rank; //[키] = 키 순위
map<int, int> rank_height; //[키 순위] = 키

vector<int> rank_cnt(100005, 0); //[키 순위] = 해당 키의 개수
vector<int> sum_sgmtt(100005 * 4, 0); //rank_cnt로 만든 세그먼트 트리

int make_sgmtt(int here, int range_left, int range_right) {

	if (range_left == range_right) {
		return sum_sgmtt[here] = rank_cnt[range_left];
	}

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (range_left + range_right) / 2;
	return sum_sgmtt[here] = make_sgmtt(left_child, range_left, mid) + make_sgmtt(right_child, mid + 1, range_right);
}

int query_sgmtt(int here, int range_left, int range_right, int find_left, int find_right) {

	if (find_left <= range_left && range_right <= find_right) {
		return sum_sgmtt[here];
	}

	if (find_right < range_left || range_right < find_left) {
		return 0;
	}

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (range_left + range_right) / 2;
	return query_sgmtt(left_child, range_left, mid, find_left, find_right) + query_sgmtt(right_child, mid + 1, range_right, find_left, find_right);
}

int update_sgmtt(int here, int range_left, int range_right, int update_index) {

	if (range_left == range_right && range_right == update_index) {
		return sum_sgmtt[here] = rank_cnt[range_left];
	}


	if (update_index < range_left || range_right < update_index) {
		return sum_sgmtt[here];
	}

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int mid = (range_left + range_right) / 2;
	return sum_sgmtt[here] = update_sgmtt(left_child, range_left, mid, update_index) + update_sgmtt(right_child, mid + 1, range_right, update_index);
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		height.push_back(input);
	}

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		s.push_back(input);
	}

	sort(height.begin(), height.end());

	int this_rank = 0;
	for (int i = 0; i < height.size(); i++) {

		if (i == 0) {
			height_rank.insert(make_pair(height[i], this_rank));
			rank_height.insert(make_pair(this_rank, height[i]));
			rank_cnt[this_rank]++;

			continue;
		}

		if (height[i - 1] < height[i]) {
			this_rank++;
		}

		height_rank.insert(make_pair(height[i], this_rank));
		rank_height.insert(make_pair(this_rank, height[i]));
		rank_cnt[this_rank]++;
	}

	make_sgmtt(0, 0, n - 1);

	vector<int> result_rank;

	//수열 s의 마지막번째부터 어떤 순위인지 찾는다
	for (int i = n - 1; i >= 0; i--) {

		int front_min_cnt = s[i]; //자신보다 작거나 같은 앞 사람의 수
		front_min_cnt++; //자신 포함하기

		int left = 0;
		int right = n - 1;
		int this_rank = -1;
		while (left <= right) {
			int mid = (left + right) / 2;

			//0~mid 순위의 사람 수의 합이 front_min_cnt개 이상일때
			if (query_sgmtt(0, 0, n - 1, 0, mid) >= front_min_cnt) {
				this_rank = mid;
				right = mid - 1;
			}

			else {
				left = mid + 1;
			}
		}

		result_rank.push_back(this_rank);
		rank_cnt[this_rank]--; //다음 앞에것에서 세지 않게 하나 줄이기
		update_sgmtt(0, 0, n - 1, this_rank);
	}

	reverse(result_rank.begin(), result_rank.end());

	for (int i = 0; i < result_rank.size(); i++) {
		cout << rank_height[result_rank[i]] << "\n";
	}

	return 0;
}