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

1. 속도 개선 아이디어

시작점이 같은 판자들이 여러개 있을 때, 이들을 모두 기억할 필요가 없다.

 

(판자1) ---------

(판자2) --------------

 

(판자1)에 못이 박힌다면, (판자2)는 자동으로 못이 박힌다.

 

2. 코드 (C++)

multimap을 map으로 수정했다.

시작위치가 같은 판자들은 가장 짧은 판자만 기억하면 된다.

#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 //update, 짧은 판자로 기억한다 
        {
            if(B[i] < it->second) it->second = B[i];
        }
    }

    int i = 0;
    for(i = 0; i < (int)C.size(); i++)
    {
        auto it = planks.begin();
        while(it != planks.end())
        {
            if(C[i] < it->first) break;

            if(it->first <= C[i] && C[i] <= it->second)
            {
                it = planks.erase(it); //못질이 되면 삭제한다
                if(planks.empty()) break;
            }
            else
            {
                it++;
            }
        }

        if(planks.empty()) break;
    }

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

 

3. 결과