[C++로 풀이] 징검다리 건너기 (이분탐색)⭐⭐⭐

📌 징검다리 건너기

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 (이분탐색)

stones의 크기(디딤돌의 개수)는 최대 200,000 개이기 때문에 O((\N^2\)) 시간복잡도부턴 시간 초과가 발생하게 될 것이다. 그러니 최대 몇 명까지 징검다리를 건널 수 있을지 일일이 이번엔 몇명 건넜다, 몇명 건넜다 하며 매번 stones를 순회하는 방식으로 풀이한다면 O((\N^2\))에 도달하여 시간 초과가 발생할 것이다.

최대 몇 명까지 징검다리를 건널 수 있을지 일일이 연산해보지말고, “최대 몇명까지 징검다리를 건널 수 있는지”를 Key 로 삼아 Up & Down 게임으로 맞춰보는 방식은 어떨까?

즉, 이 문제를 이분 탐색으로 접근해 볼 수 있다. “최대 몇명까지 징검다리를 건널 수 있는지”를 key로 지정하여, 이 Key 최대한 근접하도록 Up & Down 게임을 진행해보는 것이다.

1. 고정적으로 정해져있는 것은 무엇인가? (Up & Down 판단 기준이 될 수 있다.
   • 👉 k는 테케마다 고정적으로 주어지는 것이다. 즉, 한번에 건너 뛸 수 있는 디딤돌의 최대 칸 수. 이걸로 Up & Down 을 판단할 수 있을 것이다.
2. 무엇을 이분 탐색으로 찾을 것인가 (mid 로 업데이트 해나갈 것)
   • “최대 몇 명까지 징검다리를 건널 수 있을지”
3. 찾으려고 하는 것이 속한 범위가 정렬이 되어 있는가
   • 최소값은 1로 설정하고 최대값은 stones의 최대값으로 설정하면 즉 1,2,3,.. 같은 형태이므로 정렬되어 있다고 할 수 있다. 이 곳에서 “최대 몇 명까지 징검다리를 건널 수 있을지”를 Up & Down 방식으로, 즉 이분 탐색 방식으로 찾아 나간다.
   • 문제에선 니니즈 친구들의 수는 무제한이라고 했지만, 사실 돌은 밟을 때마다 숫자가 1씩 감소하고, 가장 가까운 디딤돌로만 건널 수 있으며 모든 돌의 숫자가 0 이 되면 이젠 아무도 건널 수 없게 되기 때문에 건널 수 있는 사람의 최대 수는 stones의 최대값, 즉 디딤돌에 적힌 숫자 중 가장 큰 숫자나 다름 없다. 한 사람이 건널 때마다 현재 존재하는 모든 돌을 밟기 떄문이다.

이분 탐색 유형의 다른 문제 참고 [고득점Kit][이분탐색] 입국심사 ⭐⭐⭐ , [고득점Kit][이분탐색] 징검다리 ⭐⭐⭐⭐

---

범위를 Up 하여 좁히는 조건과 범위를 Down 하여 좁히는 조건 (범위는 “최대 몇 명까지 징검다리를 건널 수 있을지” 그 사람 수에 대한 후보들)

• 💡 더 큰 수의 범위로 좁히는 조건 (start = mid + 1)
  • mid 명이 돌을 건넌다고 했을 때 연속으로 0 이 되는 돌의 개수(= 건너뛰는 거리)가 k보다 작을 때
    • 즉, mid 명이 돌을 건널 때 충분히 k보다 작은 수의 돌을 건너 뛸 수 있다는 얘기이므로 답은 좀 더 커도 된다.
  • “최대” 몇 명 건널 수 있을지를 구하는 것이므로 딱 떨어지지 않을 수도 있다. 그렇기 때문에 이렇게 k 이하로 건널 수 있는 충분한 경우에 해당할 때 answer 를 미리 업데이트 해놔야 한다. “최대”로 건널 수 있는 사람 수를 구하는 것이니까.
• 💡 더 작은 수의 범위로 좁히는 조건 (end = mid - 1)
  • mid 명이 돌을 건넌다고 했을 때 연속으로 0 이 되는 돌의 개수(= 건너뛰는 거리)가 k보다 클 때
    • 즉, mid 명이 돌을 건너면 불가피하게 k 보다 큰 수의 돌을 넘어야 한다는 것이다. 이는 불가능하므로 답이 될수 없다. 답은 더 작아져야 한다. 즉, 이거보다 더 적은 사람이 돌을 건널 때 k 이하로 돌을 건너 뛸 수 있게 된다는 이야기니까!

---

🔥 1 차 풀이 ❌ (정확성 3번, 효율성 13번만 틀림ㅠㅠ)

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

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int start = 1;
    int end = *max_element(stones.begin(), stones.end());
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2; // 이번 Up & Down 의 `Key` (= 현재 건너는 사람 수)

        int serialZero = 0; // 연속으로 등장한 0 의 개수
        int maxSerialZero = 0; // 현재까지의 가장 큰 연속으로 등장한 0 의 개수 (0이 연속으로 가장 많이 등장했던 구간의 0의 연속 등장 개수) 
        /* 이번 mid (현재 건너는 사람 수)이 다 건너려면 최대 얼만큼 칸 수의 돌을 건너뛰어야 하는지 계산해보기*/
        vector<int> temp_stones(stones); 
        for (int i = 0; i < temp_stones.size(); ++i) {
            // 돌의 숫자에서 현재 건너는 사람 수인 mid 를 빼야 한다. 돌은 한 사람이 건널 때마다 밟히기 때문이다.
            // 음수면 그냥 0 으로 처리 되도록 
            // A 0 0 0 B 이건 A 에서 B 로 갈 땐 4 칸 건너뛰어야 한다는 소리이다. 즉, 연속 0 의 개수보다 1 더한게 건너뛴 칸 수가 된다.  
            temp_stones[i] = (temp_stones[i] - mid + 1) > 0 ? temp_stones[i] - mid + 1 : 0; 
            if (temp_stones[i] == 0)
                serialZero++;
            else {  // 0이 아닌 돌이 등장했다면 연속 0 등장 구간 끊긴 것이므로 
                maxSerialZero = max(maxSerialZero, serialZero);
                serialZero = 0;
            }
        }

        /* Up & Down 결정 (답의 범위 좁히기) */
        if (maxSerialZero < k) { // 이번 mid는 돌을 건너뛰는 최대 수(연속 0의 등장 최대 개수)가 k 를 넘어서지 않는다면 
            answer = mid; // 건널 수 있는 경우 중 "최대 명수"를 구하는 것이므로 답이 될 수도 있으니 answer 에 저장한다. 
            start = mid + 1; // 범위를 더 넓힌다. k 이하로 돌을 건너 뛸 수 있었으니 더 많은 사람이 건너뛰도록 해볼 수 있다.
        }
        else if (maxSerialZero >= k) //이번 mid는 돌을 건너뛰는 최대 수(연속 0의 등장 최대 개수)가 k 를 넘어섰다면
            end = mid - 1; // 이 사람 수들로는 k 이상으로 뛰어넘어야 하니 사람 수를 줄여야 한다. 범위를 좁힌다.
    }

    return answer;
}

이 풀이는 정확성 3번, 효율성 13번이 틀린다. 그 이유는, 만약 마지막 구간이 연속 0 의 개수 최대가 되는 구간인데 stones 순회가 끝나버려 maxSerialZero = max(maxSerialZero, serialZero); 가 실행되지 못한 경우였을 것이다.

예를 들어 stones이 [2, 2, 1, 1, 1, 1] 이며 k가 3 이라면 딱 한명이 건너기만 해도 [1, 1, 0, 0, 0, 0] 이 되므로 최대로 건널 수 있는 사람 수는 딱 1 명이다. 그러나 마지막 구간은 serialZero는 4 에 도달하였는데도 불구하고 else에 해당하는 temp_stones[i] != 0 조건에 만나지 못했기 때문에 maxSerialZero에 반영되지 못했기 때문이다. 따라서 1 이 아닌 2 가 도출되게 된다.

for 문에서 어떤 특정 조건에서만 어떤 처리가 되게끔 혹은 반영이 되게끔 하는 작업을 할 때는 for문 순회가 끝나버려서 원래 반영이 됐어야 했는데 되지 못한 그런 경우를 생각했어야 했다. 다른 코테 문제에서도 이런 실수를 여러번 한적이 있었는데 ㅠㅠ 아차 싶었다. for 문이 끝나버려서 업뎃 되지 못하는게 있을지 반드시 점검을 하자!

🔥 2 차 풀이 ⭕

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

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int start = 1;
    int end = *max_element(stones.begin(), stones.end());
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;

        int count = 0;
        int maxCount = 0;
        for (int i = 0; i < stones.size(); ++i) {
            if (stones[i] < mid)
                count++;
            else {
                maxCount = max(maxCount, count);
                count = 0;
            }
        }
        maxCount = max(maxCount, count); // ⭐요거로 해결!

        if (maxCount < k) {
            answer = mid;
            start = mid + 1;
        }
        else if (maxCount >= k)
            end = mid - 1;
    }
    
    return answer;
}

• 그래서 위와 같이 for문이 끝나버려서 최대 구간을 찾았음에도 불구하고 반영되지 못했을 경우를 대비해서 for 문이 끝나고도 한번 더 maxCount = max(maxCount, count); 처리를 해주었다.
  • 마지막 구간이 연속 0 의 개수가 최대일 수도 있으니까!
• 그리고 stoned 사본인 temp_stones를 만들어서 모든 원소마다 직접 mid 를 뺴주고 할 필요 없이.. stones[i] < mid 이런 조건만 살피면 더 간단했다. 그래서 알고리즘은 동일하나 코드를 살짝만 심플하게 고쳤다.

---

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

맨 위로 이동하기

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