[고득점Kit][이분탐색] 징검다리 ⭐⭐⭐⭐

[이분탐색] 징검다리

난이도 ⭐⭐⭐⭐

💛 문제

💛 풀이

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

using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 1;  
    int start = 1;
    int end = distance;
    
    sort(rocks.begin(), rocks.end());
    
    while(start <= end)
    {
        int mid = (start + end) / 2;
            
        int gap = 0;
        int lastRock = 0;
        int removeCount = 0;
        
        for(int i = 0; i <= rocks.size(); i++)
        {
            if (i == rocks.size())
                gap = distance - lastRock;
            else
                gap = rocks[i] - lastRock;
            
            if (gap < mid)
                removeCount++;
            else if (i != rocks.size())
                lastRock = rocks[i];
        }
        
        if (removeCount > n)
            end = mid - 1;
        else
        {
            start = mid + 1;
            answer = mid;
        }
    }
    
    return answer;
}

이분 탐색

1. 고정 되어 정해져 있는 것은 무엇인지 (비교할 대상이 된다.)
   • n 제거해야 하는 바위의 수
2. 무엇을 이분 탐색으로 찾을 것인가 (mid로 업뎃 해 나갈 것)
   • ‘각 지점 사이의 최소 간격’ 즉 바위간의 최소 간격.
   • 의 최대값
3. 찾으려고 하는 것이 속한 범위가 정렬이 되어 있는가
   • ‘각 지점 사이의 최소 간격’의 범위의 최소값은 대충 1 로 상정하고 최대값은 대충 바위가 하나도 없어서 출발지점 ~ 도착지점 간의 거리인 distance로 정해놓는다.
   • 1 ~ distance 범위는 그 자체로 정렬이 되어 있다. 우리가 찾고자 하는 답인 ‘각 지점 사이의 최소 간격’는 이 정렬된 범위 내에 있으므로 이분 탐색을 사용하여 답을 찾을 수 있다.

      int start = 1;
      int end = distance;
     

• 찾고자 하는 것은 각 지점 사이의 최소 간격
• 분할 기준이 되는 비교는 제거해야할 바위 수와 현재의 mid인 각 지점 사이의 간격을 기준으로 했을 때 제거 한 바위의 수를 비교.

모든 경우의 수를 검사하지 않는다. 우리가 찾고자 하는 답인 ‘각 지점 사이의 최소 간격’을 업다운 형식으로 범위를 좁혀 나가 찾을 뿐이다. 업 다운의 기준은 정해져 있는 현재의 거리가 n개 이하로 바위를 제거하는 것이 가능한 거리인지를 따지는 것이 된다. n개 이하로 최대한 바위를 적게 제거해야 하는 이유는 거리의 최소값들 중에 가장 최대값이 되는 제거 케이스를 찾아야 하기 때문에 최대한 바위를 적게 제거 해야 한다.

• 문제에서 명확히 정해져 있는 것은 n 제거해야 하는 바위의 수.
  • ⭐현재 정해놓은 '각 지점 사이의 최소 간격'인 mid를 기준으로 했을 때의 바위 제거 가능한 수를 n과 비교하여 범위를 업데이트 및 좁혀 나간다. 👉 현재 정해둔 `mid`인 '각 지점 사이의 최소 간격' 보다 작은 간격의 바위는 제거하고 이 제거 횟수를 세자! 그리고 다 세고 난 후에 n과 비교하자!

        for(int i = 0; i <= rocks.size(); i++)
        {
            if (i == rocks.size())
                gap = distance - lastRock;
            else
                gap = rocks[i] - lastRock;
                
            if (gap < mid)
                removeCount++;
            else if (i != rocks.size())
                lastRock = rocks[i];
        }
    

    • 먼저 rocks를 정렬하여 바위의 위치들을 순서대로 정렬한다.

        sort(rocks.begin(), rocks.end());
      

    • rocks를 통해 위치별로 순서대로 바위 사이의 간격을 구한다. (바위1위치 - 출발지), (바위2위치 ~ 바위1위치), … , (마지막바위위치 - 마지막에서두번재바위위치), (도착지 - 마지막바위위치) 이렇게 총 rocks.size() + 1 개의 간격을 구해야 한다. for 문은 rocks.size() + 1 번 돌아야 함
      • if (i == rocks.size()) 마지막 간격은 (도착지 - 마지막바위위치) 값인 distance - lastRock.
      • else 그 외의 간격은 모두 rocks[i] - lastRock
    • 바위를 제거해나갈 것이기 때문에 간격을 구할 때 제거 된 바위의 그 앞 바위를 위치를 뺄셈 해주어야 한다. 따라서 이전 바위 위치를 lastRock 변수에 저장한다.
    • 바위 제거하는 기준 👉

            if (gap < mid)
                removeCount++;
            else if (i != rocks.size())
                lastRock = rocks[i];
      

      • 위에서 구한 간격 gap이 mid보다 작다면
        • 간격을 넓혀야 하므로 바위를 제거한다. removeCount 증가. for문이 끝나면 현재 mid에서의 바위 제거 수가 removeCount에 최종적으로 담기게 되고 후에 이걸 n과 비교하여 이분 탐색 범위를 좁혀나갈 것이다.
        • lastRock을 업데이트 하지 않는다. 현재 바위는 제거 되었으므로 lastRock은 그대로 이전 바위다. 현재 바위가 3바위라면 이전 바위는 2바위이고 다음 바위는 4바위 가 될텐데 4바위는 2바위와의 간격을 구하도록 lastRock을 업데이트 하지 않음.
      • 위에서 구한 간격 gap이 mid보다 크거나 작다면
        • 바위를 제거하지 않는다. 따라서 removeCount을 업데이트 하지 않는다.
        • lastRock을 업데이트 한다. 현재 바위는 제거 되지 않았으므로 다음 바위에서 간격을 잴 이전 바위를 현재 바위로 업데이트 한다.
          • 단 lastRock을 현재 바위로 업데이트 하는 과정은 현재 순회 위치가 도착지가 아닐 때만 이루어져야 한다. 도착지일 땐 i가 rocks.size() 값이니까 이를 고려하지 않으면 last = rocks[i] 에서 런타임 에러 남 !
  • for문을 돌면서 구한 현재 정해놓은 ‘각 지점 사이의 최소 간격’인 mid를 기준으로 구한 바위 제거 수인 removeCount를 n과 비교하여 이분 탐색 범위를 업데이트 한다.
    • removeCount > n : 현재 정해놓은 mid 기준에서 n 제거해야 하는 바위 보다 더 많이 제거 됐다면 현재 정해놓은 바위 간격인 mid가 너무 크다는 것이다. 더 작은 범위로 좁혀야 한다.

        if (removeCount > n)
            end = mid - 1;
      

    • removeCount <= n : 현재 정해놓은 mid 기준에서 n 제거해야 하는 바위 보다 같거나 더 적게 제거했다면 n 더 적게 제거 했다면 더 큰 mid로 간격을 더 크게 해서 더 많이 제거할 수 있도록 해야 겠지만, n과 같다면 현재의 mid가 충분하다는 것이므로 정답 후보가 될 수 있다. 더 큰 최대값이 있을 수 있으므로, 즉 더 큰 mid에서도 정답이 있을 수 있으므로 더 큰 범위로 좁힌다.
      • answer를 업데이트 한다. 현재의 mid가 답이 될 수도 있으므로.. 이게 최대값이 될 수 있다.
        • 예를 들어 현재 간격을 5로 해두었을 때 제거한 바위의 수가 n과 같았다면 5 가 정답이 될 수 있다. 그러나 5보다 더 큰 수에서도 제거한 바위의 수가 n과 같을 수 있기 때문에 일단 answer에 5를 저장 후 더 큰 값의 간격에서도 바위를 제거해 봐야 한다!

          else
          {
            start = mid + 1;
            answer = mid;
          }
          

• answer가 while문에서 한번도 업뎃되지 않을 경우를 대비하여 최소값인 1를 초기값으로 잡는다.
  • 한번도 업뎃되지 않았다는건 1 ~ 59 범위의 모든 시간이 n 명을 심사하기엔 전부 부족했다는 것이다.

    long long answer = end;
    

• 이 문제는 이분 탐색의 대표 코드에서 mid == answer가 되면 return 되어 빠져나오는 것과 다르게, 정확하게 딱 떨어지는 값을 찾는 것이 아닌 n개를 제거 할 수 있는 최소 간격 중에서도 최대 간격을 찾는 것이기 때문에 answer를 미리 업데이트 해둘 뿐, while을 탈출하는건 start > end 가 될 때 뿐이다.
  • mid == answer가 되었다고해서 바로 while문을 빠져나와 answer를 리턴하면 안된다.
• 간격의 ‘최소값’을 mid로서 정해두는 것이고 그 mid를 기준으로 구한 바위 제거 수가 n과 일치하는 것들 중 최대값이 되는 mid를 구하는 것이 목표다.
  • 이 문제에서 최소는 정해 두는 것이고, 최대값은 구해야 하는 것

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기