백준 10431 줄세우기 ( set, bst 활용 )

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

 

매번 줄을 설 때마다 자기보다 키가 큰 학생 수를 더하면 밀려난 총량이 나온다.

따라서, 기존에 줄을 선 아이들 중, 이번에 줄을 설 아이보다 키가 큰 아이의 수를 찾으면된다.

이걸 O(N)으로 탐색해도 input 이 크지 않기에 상관 없지만, BST를 구축하면 O(logN)만에 찾을 수 있기에 BST를 사용할 것이다.

추가로, vector를 써도 되지만, vector는 매번 줄을 선아이를 추가하는 insert에서 O(N)의 시간 복잡도가 든다.

 

따라서, 문제의 튜닝 포인트는 아래와 같다

1) BST를 통해 자신보다 큰 아이의 개수를 찾기

lower_bound & upper_bound 라이브러리는 bst 기반 탐색으로 자기보다 큰 키의 아이들을 찾으면 된다.

 

lower_bound

찾고자 하는 값보다 같거나 큰 숫자가 처음 등장하는 위치 반환

• 용도 1 : key 값이 가장 처음 등장하는 위치 찾을 때
• 용도 2 : key 값보다 작은 값들의 개수 구할 때

upper_bound

찾고자 하는 값을 초과하는 값이 가장 처음 나타나는 위치를 반환

• 용도 1 : key 값이 가장 마지막에 등장하는 위치 찾을 때
• 용도 2 : key 값보다 큰 값들의 개수 구할 때

 

2)  문제 조건에서 키는 중복되지 않는다는 조건과 부합하기도 하고, insert cost가 O(logN) 인 set에 줄을 선 아이들 정보를 누적한다.

 

정답

#include <string>
#include <vector>
#include<iostream>
#include<set>
using namespace std;


const int NUM = 20;


int main(){
   // 1명씩 뒤로 서는 과정에서, 물러나는 총 개수 (  물러난 사람 * 물러난 양)
    int t;
    cin>>t;
    while(t--){
        int arr[20];
        int testNum;
        cin>>testNum;
        
        for(int n=0;n<NUM;n++){
            cin>>arr[n];
        }
        set<int> sortedNumbers;
        int answer =0;
        for(auto h: arr){
            auto it = sortedNumbers.upper_bound(h);
            int tallerNum = distance(it, sortedNumbers.end());
            answer += tallerNum;
            sortedNumbers.insert(h);
        }
        cout<<testNum<<" "<<answer<<endl;
    }
}