백준 2465 - 줄 세우기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2465

 

세그먼트 트리를 이용한 문제입니다.

 

수열이 하나 주어지고, 해당 수열에서의 키 순서가 주어질 때, 키 순서에 맞는 수열을 찾는 문제입니다.

 

먼저, 자신보다 키가 작거나 같은 학생을 알기 위해서 오름차순 정렬을 해줍니다.

 

오름차순 정렬을 해줬으면, 자신이 어디에 들어가야 할지를 뒤에서부터 확인을 해줍니다.

(키 순서가 0 1 0 0 3 2 6 7 4 6 9 4 이니 4에서부터 채워줍니다.)

 

뒤에서 부터 채우는 이유는 앞에서 부터 채울 경우 0을 채워야 하는데, 해당 값이 정확하지 않기 때문입니다.

반대로 뒤에서 부터 채울 경우, 값이 0이 아닌 것부터 채우기 때문에 어떤 값을 먼저 채워야할지 명확해지기 때문입니다.

 

어떤 값이 어디에 들어가야할지 찾는 방법은 이분 탐색을 응용했습니다.

 

예를 들어서, 자신의 키보다 작거나 같은 사람이 4명이 있다면 자신은 5번째에 들어가야할 수입니다.

1. 12개의 값을 기준으로 앞의 6개와 뒤의 6개 중, 앞 쪽에 들어가야 합니다.

2. 앞의 6개 중에서, 다시 앞의 3개와 뒤의 3개로 나눠줍니다. 이때는 뒤의 3개의 수에 들어가야합니다.

    2-1. 뒤의 순서에 들어가게 되었다면, 해당하는 앞의 수 개수를 빼줘야합니다. 따라서 5 - 3인 2번째 수로 바뀝니다.

3. 뒤의 3개의 수를 앞의 2개, 뒤의 1개로 바꾸고, 앞의 2개에 속하니 해당 위치로 가줍니다.

4. 2개의 수 중, 뒤에 속하니 해당 위치로 넘어가고 위치가 정해졌으니 해당 수의 탐색을 종료합니다.

 

-> 해당 방식으로 반을 나눠 어디에 속하는지 확인하는 과정을 반복해주면 됩니다.

     위치가 정해진 수가 있다면, 거쳐온 위치들에서 값을 -1을 해줍니다.

    (거쳐왔다는 것은 해당 위치들에서 값이 하나 채워졌다는 의미임으로 채울 수 있는 값을 1을 빼줍니다.)

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

int N;
int Tree[100001 * 4];
int height[100001 * 4];
int remake[100001 * 4];
int Rank[100001 * 4];
int ans[100001 * 4];

void make_tree(int node, int st, int fin){
	if(st == fin) {
		Tree[node] = 1;
		return;
	}
	int left = node * 2;
	int right = node * 2 + 1;
	int mid = (st + fin) / 2;
	make_tree(left, st, mid);
	make_tree(right, mid + 1, fin);
	Tree[node] = Tree[left] + Tree[right];
}

void update_tree(int node, int st, int fin, int target, int idx){
	Tree[node]--;
	if(st == fin){
		ans[idx] = height[st];
		return;
	}
	int left = node * 2, right = node * 2 + 1;
	int mid = (st + fin) / 2;
	if(target <= Tree[left]){
		update_tree(left, st, mid, target, idx);
	}
	else{
		update_tree(right, mid + 1, fin, target - Tree[left], idx);
	}
}

void solve(){
	//find_height(1, N);
	sort(height + 1, height + N + 1);
	make_tree(1, 1, N);
	for(int i = N; i > 0; i--){
		update_tree(1, 1, N, Rank[i] + 1, i);
	}
	for(int i = 1; i <= N; i++) cout << ans[i] << "\n";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++) scanf("%d", &height[i]);
	for(int i = 1; i <= N; i++) scanf("%d", &Rank[i]);
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.