백준 2465번 줄 세우기

문제

N명의 사람들이 어떤 공연장에 입장하기 위해서 한 줄로 서 있다. 줄 서 있는 각 사람은 자기 앞에 서 있는 사람들 중에서 자기보다 키가 작거나 같은 사람들의 수를 알고 있다. 그러면, 이 수들을 표시하는 수열을 S라고 한다.

N명의 키 집합과 수열 S가 주어질 때, 원래 줄 서 있는 키 순서를 정확히 찾아내는 프로그램을 작성하시오. 

예를 들어서, 사람들의 키 집합이 다음과 같이 주어진다 (여기서, 같은 키의 사람들이 여러 명 존재할 수 있어서 중복이 포함된다). 

{120, 167, 163, 172, 145, 134, 182, 155, 167, 120, 119, 156}

또한 각 사람이 자기 앞에 있는 사람들 중에서 자기보다 키가 작거나 같은 사람들의 수를 표시하는 수열 S는 다음과 같이 주어진다. 

S :   0 1 0 0 3 2 6 7 4 6 9 4

그러면, 실제 줄 서 있는 사람들의 키 순서는 다음과 같다. 

134 167 120 119 156 120 167 182 155 163  172 145

문제풀이

사용한 알고리즘 : segtree

(0) 생각

 문제의 예시에 대해 생각해 봅시다.

Index	0	1	2	3	4	5	6	7	8	9	10	11
키	119	120	120	134	145	155	156	163	167	167	172	182
순서	0	1	0	0	3	2	6	7	4	6	9	4
누구꺼

 주어진 순서의 뒤에서부터 탐색을 할 것입니다.

 1] 11 번째 서있는 사람 앞에 있는 작은 사람 수 : 4 

    자신의 앞에 4명의 작은 사람이 있어야 하므로 이 사람 키는 145 입니다.

Index	0	1	2	3	4	5	6	7	8	9	10	11
키	119	120	120	134	145	155	156	163	167	167	172	182
순서	0	1	0	0	3	2	6	7	4	6	9	4
누구꺼					11

    4번째 145 는 11번째 서있는 사람이 가져갔음을 체크해줍니다.

 2] 10 번째 서있는 사람 앞에 있는 작은 사람 수 : 9 

    이미 쓰인 4번째 키(145) 제외하고 9명이 있어야 하므로 이 사람 키는 172입니다.

Index	0	1	2	3	4	5	6	7	8	9	10	11
키	119	120	120	134	145	155	156	163	167	167	172	182
순서	0	1	0	0	3	2	6	7	4	6	9	4
누구꺼					11						10

    10번째 172 는 10번째 서있는 사람이 가져갔음을 체크해줍니다.

 3] 9번째 서있는 사람 앞에 있는 작은 사람 수 : 6

    이미 쓰인 4번째, 9번째 키는 제외 하고 6명의 작은 사람이 있어야 하므로 키는 163입니다.

Index	0	1	2	3	4	5	6	7	8	9	10	11
키	119	120	120	134	145	155	156	163	167	167	172	182
순서	0	1	0	0	3	2	6	7	4	6	9	4
누구꺼					11			9			10

    7번째 163 은 9번째 서있는 사람이 가져갔음을 체크해줍니다.

이 과정을 반복하여 아래와 같이 표를 완성할 수 있습니다.

Index	0	1	2	3	4	5	6	7	8	9	10	11
키	119	120	120	134	145	155	156	163	167	167	172	182
순서	0	1	0	0	3	2	6	7	4	6	9	4
누구꺼	3	2	5	0	11	8	4	9	1	6	10	7

 이에따라 0번째 사람 키 : 134

                1번째 사람 키 : 167

                2번째 사람 키 : 120

                    ...

                11번째 사람 키 : 145 임을 알 수 있습니다.

(1) 코드 34~37

 입력된 서있는 순서를 뒤에서부터 탐색하며, 해당 사람이 갖는 키를 찾아줍니다.

 찾은 키를 가져갔음을 체크해줍니다.

(2) 코드 17~26

 매 탐색 시, 이미 앞에서 몇몇의 키를 가져간 상태에서, 앞에 x명 있으려면 키는 무엇일지 찾는 함수를 구현하였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 1 << 17;
	int N;
	int tall[MAX];
	int sequence[MAX];
	int ans[MAX];
	int segtree[2 * MAX];
	void update(int x) {
	while (x > 0) {
	segtree[x]++;
	x /= 2;
	}
	}
	// s~e 범위에서 wanna의 키를 갖은 사람이 몇번째로 큰 사람인지 구하는 함수
	int path(int wanna, int idx = 1, int s = 0, int e = MAX - 1) {
	if (idx >= MAX) return idx - MAX; // 기저 (wanna의 키를 갖은 사람이 들어갈 자리)
	int mid = (s + e) / 2;
	int left_seat = (mid - s + 1) - segtree[2 * idx]; // 왼쪽에 남은 자리
	if (left_seat >= wanna) return path(wanna, 2 * idx, s, mid);
	else return path(wanna - left_seat, 2 * idx + 1, mid + 1, e);
	}
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> tall[i]; // 실제 키
	for (int i = 0; i < N; ++i) cin >> sequence[i]; // 앞에 있는 작은 사람 수 수열
	sort(tall, tall + N); // 키순으로 정렬
	for (int i = N - 1; i >= 0; i--) { // 뒤에서 부터 탐색
	ans[i] = path(sequence[i] + 1);
	update(MAX + ans[i]); // 해당 키 가져갔음을 체크
	}
	for (int i = 0; i < N; ++i) cout << tall[ans[i]] << '\n';
	return 0;
	}

view raw BOJ 2465.cpp hosted with ❤ by GitHub