C++/알고리즘
숫자 게임(BST)
K.DJ
2023. 8. 18. 15:14
https://school.programmers.co.kr/learn/courses/30/lessons/12987
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
상대의 숫자를 선형탐색하면서 상대의 숫자보다 크면서 최소인 값을 구하면 된다.
없다면 갖고있는 숫자 중 최소값을 사용한다.
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;
}