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

programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

<풀이>

1. 징검다리 정보와 한번에 건너뛸 수 있는 칸 수를 입력받는다.

2. 징검다리를 건널 수 있는 최대 사람 수를 반환한다.

 

<해법>

1. 징검다리를 건널 수 있는 최대 사람수를 구하는 방법

=> 이 문제는 "효율성 테스트"가 있는 문제입니다. 정확한 구현을 요구하는 문제가 아닌, 특정 알고리즘이나 자료구조를 묻는 문제입니다. 저는 이분탐색이 떠올랐고, 사람 수를 이분탐색하는 방식으로 구현하였습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//해당 사람의 수가 징검다리를 건널 수 있는지 확인하는 함수
bool canCross(vector<int> stones, int peopleCnt, int k) {
 
    int stoneCnt = 0;
    for (int i = 0; i < stones.size(); i++) {
        if (stones[i] - peopleCnt < 0) {
            stoneCnt++;
            if (stoneCnt >= k) {
                return false;
            }
        }
        else {
            stoneCnt = 0;
        }
    }
    return true;
}
 
int solution(vector<int> stones, int k) {
    int answer = 0;
 
    /* 해법 */
    //건널 수 있는 사람의 수를 이분탐색
    int start = 0;
    int end = *max_element(stones.begin(), stones.end());
 
    while (start <= end) {
        int mid = (start + end) / 2;
 
        //mid수의 사람이 건널 수 있는지 확인
        if (canCross(stones, mid, k)) {
            answer = mid;
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
 
    //결과 반환
    return answer;
}

 

이분탐색에 대해 알아볼 수 있는 문제였습니다.