[프로그래머스] 징검다리 건너기

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

효율성 테스트가 있는 문제이다. 따라서 효율성이 중요한 문제인데, 이 문제는 이분탐색을 사용해서 해결할 수 있다. 이분 탐색에서 가장 중요한 것은 '어떤 값을 기준으로 정할 것인가'이다. 아래의 코드에서는 니니트 프렌즈를 번호를 기준으로 했다. m번째 인원이 건널 때 디딤돌의 숫자는 stones[i] - m 이 되고, 이를 통해 건널 수 있는지 없는지를 파악해 이분 탐색해서 해결해주었다.

코드

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// m번째 인원이 건널 수 있는지 확인
bool can_move(vector<int>& stones, int k, int m) {
    int cnt = 0;
    for (int i = 0; i < stones.size(); i++) {
        if (stones[i] - m <= 0) cnt++;
        else cnt = 0;
        if (cnt == k) return false;
    }
    return true;
}

int solution(vector<int> stones, int k) {
    int size = stones.size();
    int left = 1;
    int right = *max_element(stones.begin(), stones.end());

    while (left <= right) {
        int mid = (left + right) / 2;

        if (can_move(stones, k, mid)) left = mid + 1;
        else right = mid - 1;
    }
    int answer = left;
    return answer;
}