백준 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명 있으려면 키는 무엇일지 찾는 함수를 구현하였습니다.