Lesson 14. Binary search algorithm - NailingPlanks #3 (속도 개선)

1. 속도 개선 아이디어

주제가 이진탐색인데, 아직까지 이진탐색을 시도하지 않았다.

map은 find함수를 통해 이진탐색을 제공하지만, 처음에 판자를 정리할 때만 잠깐 사용했고, 이후 못질하는 곳에서는 전혀 사용되지 않았다.

 

못질하는 곳에 이진탐색을 사용해보자.

 

 

2. 코드 (C++)

현재 자료형은 map이므로, 항상 순회해야 한다. 

중간위치에 바로 접근하기 위해 판자들을 vector에 옮겨 담았다.

#include <map>

int solution(vector<int> &A, vector<int> &B, vector<int> &C) {

    map<int, int> planks = {};
    for(size_t i = 0; i < A.size(); i++)
    {
        auto it = planks.find(A[i]);
        if(it == planks.end())
        {
            planks.insert({A[i], B[i]});
        }
        else
        {
            if(B[i] < it->second) it->second = B[i];
        }
    }

    //판자를 vector에 저장한다
    vector<pair<int, int>> boards = {};
    for(const auto p : planks)
    {
        boards.emplace_back(p.first, p.second);
    }

    int i = 0;
    for(i = 0; i < (int)C.size(); i++)
    {
        int left = 0;
        int right = boards.size() - 1;
        while(left <= right)
        {
            int mid = (left + right) / 2;

            //가지고 있는 판자들 중,
            //가운데 판자를 골라서, 현재의 못이 박히는지 확인한다
            if(boards[mid].first <= C[i] && C[i] <= boards[mid].second)
            {
                boards.erase(boards.begin() + mid); //못질이 되면 삭제한다
                if(boards.empty()) break;
                right--;
            }
            else if(C[i] < boards[mid].first) //못질할 수 없다면, 탐색 범위 조정
            {
                right = mid - 1;
            }
            else if(C[i] > boards[mid].second) //못질할 수 없다면, 탐색 범위 조정
            {
                left = mid + 1;
            }
        }

        if(boards.empty()) break;
    }

    if(boards.empty()) return i + 1;
    return -1;
}

 

 

3. 결과

마지막 테스트 속도가 상당히 올라갔지만, 여전히 통과하지 못했다.