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

1. 속도 개선 아이디어

이진 탐색 대상을 바꿔보자.

 

AS_IS: 어떤 판자에다가 못질을 할까?

TO_BE: 몇 번째 못을 사용하면, 모든 판자에 못질이 될까? 

 

그런데 못은 순서대로 사용해야 한다. 

따라서 이진 탐색으로 3번째 못을 골랐다면, 1, 2번째 못을 사용해야한다.

이러면, 1번째, 2번째, 3번째, 순차적으로 못질하는 것과 같지 않을까? 

 

이를 해결하기 위해선, 이번에도 생각의 전환이 필요하다.

못을 들고, 판자에다가 하나하나 박을게 아니라, 

현재까지 사용된 못 상태를 놓고, 판자를 못 상태에 대조하는 형태로 가야한다.

 

예시)

C[0]	C[1]	C[2]	C[3]	C[4]
4	6	7	10	2

 

이를 배열로 표현해보면 다음과 같다.

1	2	3	4	5	6	7	8	9	10
	못		못		못	못			못

 

C[0] 못을 골랐다고 생각해보자.

못의 상태 배열은 다음과 같을 것이다.

1	2	3	4	5	6	7	8	9	10
			못

 

C[2] 못을 고르면 다음과 같다.

1	2	3	4	5	6	7	8	9	10
			못		못	못

 

C[2] 못 상태 배열에다가 판자를 비교해보자.

판자 [1, 4] 못 있음

판자 [4, 5] 못 있음

판자 [5, 9] 못 있음

판자 [8, 10] 못 없음

 

2. 코드(C++)

#include <map>

bool check(int mid, map<int, int>& planks, vector<int>& C)
{
    //못 상태 배열 생성
    //문제에서 C가 가질 수 값의 범위는 1 ~  M * 2 였다
    //M은 C의 개수이므로, 상태 배열의 크기는 (C.size() * 2 + 1)이 되어야 한다
    vector<bool> nails(C.size() * 2 + 1, false);
    for(int i = 0; i <= mid; i++)
    {
        nails[C[i]] = true;
    }

    //판자에 못이 있는지 없는지 확인
    auto it = planks.begin();
    while(it != planks.end())
    {
        int start = it->first;
        int end = it->second;
        bool is_nailed = false;
        while(start <= end)
        {
            if(nails[start])
            {
                is_nailed = true;
                break;
            }
            else
            {
                start++;
            }
        }

        if(is_nailed == false) return false;
        it++;
    }

    return true;
}

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];
        }
    }

    int left = 0;
    int right = C.size() - 1;
    int min_nail = -1;
    while(left <= right)
    {
        int mid = (left + right) / 2; //가운데 못 선택
        
        bool result = check(mid, planks, C);
        
        //현재 못으로 성공했다면, 
        //더 작은 개수의 못으로도 성공할 수도 있으니, 탐색을 더 해봐야 한다
        if(result)
        {
            right = mid -  1;
            min_nail = mid + 1; //성공한 못의 개수 기록
        }
        else // 실패했다면, 현재 못으로는 부족한 것이다
        {
            left = mid + 1;
        }
    }

    return min_nail;
}

 

3. 결과