[프로그래머스/C++] 징검다리 건너기 (2019 카카오 개발자 겨울 인턴십)

 

 

문제

문제 설명

 

 

 

 

풀이

 

[문제 풀이]

 

문제를 푸는 방법이 몇 개 생각났지만, 그 중에서도 이분탐색으로 몇 명이 건널 수 있는지를 먼저 선택하고 실제로 건널 수 있는지를 체크하는 방법이 빠르다고 생각했다.

 

생각한 방법들 중 하나를 소개하자면, k개 만큼의 돌들을 탐색하고 그중에 max값을 찾으면 max 값을 저장하고 그 이후의 돌 부터 다시 k개 돌을 탐색해 max값이 얼마인지 찾으면서 탐색하는 방법이다. 대신 이 방법을 쓰게 되면 우선순위 queue가 필요하고, 우선순위 queue를 쓰더라도 edge case가 생길 여지가 있어 이분탐색 방법을 선택했다.

 

이분 탐색으로 n명이 건널 수 있다고 가정할 경우

1. 만약 n보다 같거나 작은돌이 연속으로 n개 이상 나오면, 이 경우에 n명은 건널 수 없다는 뜻이다.

2. 반대로 n보다 같거나 작은돌이 연속으로 나오는 수가 n개 보다 작다면 이 경우는 n명이 건널 수 있다는 뜻이 된다.

 

여기서 1번일 경우 n명보다 인원이 작아져야하므로 ed를 n-1로 바꾸고 다시 탐색했다.

만약 2번일 경우 n명보다 인원이 많을 수 있으므로 st를 n+1로 바꾸고 다시 탐색했다.

(편의를 위해 mid가 중앙 값, st를 이분탐색에서 왼쪽, ed를 오른쪽으로 사용했다)

 

그러다 st가 ed보다 커지면 이 때 st에 저장된 값이 최대 건널 수 있는 인원이므로 st를 return하면 된다.

 

[아이디어 정리]

1. 최소 건널 수 있는 인원을 1 (st) , 최대 건널 수 있는 인원을 200,000,000 (ed) 으로 설정하고 이분탐색을 한다.
2. 이분 탐색으로 결정된 인원이 n 일 때, n보다 작은 수를 가진 돌이 연속으로 n개 나오면 ed를 n-1로, 반대로 n보다 작은 수를 가진 돌이 연속으로 n개 이상 나오지 않는다면 st를 n+1로 설정하고 다시 탐색한다.
3. st가 ed보다 클 경우 이분 탐색을 멈추고 st를 return 한다.

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> stones, int k) {
    int st = 1, ed =200000000,mid, cCnt;
    bool flag=true;
    // 인원을 기준으로 이분탐색
    while(st<=ed)
    {
        mid =(st+ed)/2;
        cCnt=0;
        flag = true;
        for (int i=0; i<stones.size(); i++)
        {
            if (stones[i]<=mid)
            {
                cCnt+=1;
                if (cCnt>=k)
                {
                    ed=mid-1;
                    flag=false;
                    break;
                }
            }
            else
            {
                cCnt=0;
            }
        }
        if (flag)
        {
            st=mid+1;
        }
    }
    return st;
}

 

---

 

잘 풀렸지만, 뭔가 다양한 생각을 할 수 있는 문제가 있으면 좋을 것 같다...

 

프로그래머스