숫자 게임(BST)

https://school.programmers.co.kr/learn/courses/30/lessons/12987

프로그래머스

 

상대의 숫자를 선형탐색하면서 상대의 숫자보다 크면서 최소인 값을 구하면 된다.

없다면 갖고있는 숫자 중 최소값을 사용한다.

 

A의 숫자마다 B의 모든 숫자를 탐색한다면 N^2의 시간이 소요되므로 이진탐색트리를 사용하도록 한다.

이진 탐색의 lower bound, upper bound의 활용을 보는 문제라고 생각된다.

 

set.lower_bound(): 특정 값 이상의 값이 처음 나타나는 위치를 반환한다.

set.upper_bound(): 특정 값을 초과하는 값이 처음 나타나는 위치를 반환한다.

set.begin(): 시작 지점을 반환한다. set은 이진탐색트리 구조이므로 루트의 이터레이터를 반환하게 된다.

 

lower_bound와 upper_bound 함수는 algorithm 헤더에도 존재하며 배열 혹은 벡터를 받아 작동한다.

단, 이 때 파라미터로 전달되는 배열이나 벡터는 오름차순으로 정렬되어 있어야 한다.

 

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

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    multiset<int> ms;
    for (int n : B)
    {
        ms.insert(n);
    }
    for (int a : A)
    {
        auto iter = ms.upper_bound(a);
        if (iter == ms.end())
        {
            ms.erase(ms.begin());
        }
        else
        {
            ++answer;
            ms.erase(iter);
        }
    }
    return answer;
}