프로그래머스 - 숫자 게임 [C++]

 이 문제는 프로그래머스 level 3 문제이다. 나는 처음에 이 문제를 이분 탐색을 통해서 풀려고 했다. 그래서 upper_bound를 이용한 뒤 erase를 하는 방식으로 구현했는데, 이런 식으로는 답은 나오나 시간 초과가 떴다. 내가 생각했을 때에는 vector 내의 erase 함수가 내부적으로 O(n) 이 걸리기 때문에 입력이 100000까지 나오는 경우 O(n^2)은 불가능하기 때문이라고 생각했다. 그래서 다른 풀이를 보니 투 포인터를 이용해서 간단하게 풀 수 있었다. 

 

 요즘 문제를 풀다 보면 이분 탐색이 가능한 문제는 보통 투 포인터로도 풀린다는 연관성이 보인다. 물론 입력이 O(n) 으로도 안될 정도로 큰 문제는 이분 탐색밖에 안되겠지만, O(n) 으로도 가능한 입력은 투 포인터도 사용 가능하다는 사실을 기억해야겠다. 왜냐하면 투 포인터로 문제를 해결하는게 상당히 직관적이고 디버깅이 쉽기 때문이다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int aIndex = 0;
    int bIndex = 0;
    
    while (aIndex < A.size() && bIndex < B.size()) {
        if (A[aIndex] < B[bIndex]) {
            answer++;
            aIndex++;
            bIndex++;
        }
        else {
            bIndex++;
        }
    }
    
    return answer;
}