[카카오 기출] 징검다리 건너기(풀이,설명) - C++

문제 출처

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

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

문제가 매우 길어요. 여기서 문제 푸는 데 중요한 내용만 뽑으면 아래와 같습니다.

(니니즈 친구들이 사람은 아니지만 편의를 위해 사람 수라고 표현했습니다. ㅎㅎ)

 

• 징검다리를 누군가 건널 때마다 해당 다리의 원소가 1 감소하고 0이 되면 건널 수 없으므로 징검다리의 각 원소 값은 그 다리를 건널 수 있는 사람의 수와 관련 있음 (매우 중요한 포인트입니다.)
• 우리는 결국 건널 수 있는 사람 수를 구하고 싶은 거고, stones 배열의 원소 값이 각각 1이상 200,000,000이하이므로 우리가 구하고자 하는 값, 즉 사람 수의 범위가 엄청 큰 겁니다. -> 이분탐색을 활용해야 시간초과를 막을 수 있어요.
• 건널 수 있는 사람 수를 mid값으로 해서 이분 탐색을 해 나갈 겁니다.
• mid값 만큼의 니니즈 친구들이 모두 건널 수 있는 지 탐색하려면, 건너뛰는 칸 수가 k이내인지를 확인해야 합니다.
• 여기서 또 중요한 것은, 건너는 칸 수가 k이지 건너는 징검다리의 수가 k가 아닙니다. (이걸 놓쳐서 틀린 원인을 찾기가 많이 어려웠습니다. 문제 예시 그림 보시면서 둘의 차이를 잘 파악하셔야 해요.)

코드 보고, 아래에 이어서 풀이합니다.

 

주석 없는 코드

 

#include <string>
#include <vector>
using namespace std;
bool jump(vector<int>stones, int k, int mid){
    int jump =0;
    for(int i=0; i<stones.size();i++){
        if(mid > stones[i]){
            jump++;
            if(jump>k-1){
            return false;
            }
        }
        else {
            jump =0;
        }
    }
    return true;
}
int solution(vector<int> stones, int k) {
    int answer = 0;
    long long left = 1;
    long long right = 200000000;
    long long mid;
    while(left <=right){
        mid = (left+right)/2;
        bool result = jump(stones,k,mid);
        if(result)
            left = mid+1;
        else
            right=mid-1;
    }
    answer = right;
    return answer;
}

 

주석 있는 코드

 

#include <string>
#include <vector>
using namespace std;
bool jump(vector<int>stones, int k, int mid){//mid명이 건널 수 있는 지 파악하는 함수
    int jump =0;
    for(int i=0; i<stones.size();i++){
        if(mid > stones[i]){//못 건너는 다리의 수가 jump변수, 못 건너는 칸 수 아님!! 다리 개수임!
            //k칸을 뛸 수 있단 건 건너지 못하는 다리가 k-1개까지 가능하다는 의미
            jump++;
            if(jump>k-1){
            return false;
            }
        }
        else {
            jump =0;
        }
    }
    return true;
}
int solution(vector<int> stones, int k) {
    int answer = 0;
    long long left = 1;
    long long right = 200000000;//건널 수 있는 사람 수 최대 범위
    long long mid;
    while(left <=right){
        mid = (left+right)/2;
        bool result = jump(stones,k,mid);
        if(result)
            left = mid+1;
        else
            right=mid-1;
    }
    answer = right;
    return answer;
}

 

문제풀이

 

solution 함수 :

이분탐색의 주인공은 위에서 언급한 바와 같이 건널 수 있는 사람 수가 됩니다.

이 범위는 한 징검다리의 원소가 가지는 값의 범위와 같으므로 left는 1, right은 2억이에요.

mid값을 이분탐색으로 탐색해 나가고 jump함수를 통해 현재 mid명이면 다리를 건널 수 있는 지 파악해서 적절한 mid값을 찾습니다.

 

jump 함수 :

현재의 mid명이면 다리를 건널 수 있는 지 파악하는 함수입니다.

 

한 칸씩 징검다리를 돌면서(stones) 건너뛰어야 하는 다리의 수를 jump라는 변수로 세었습니다.

여기서, 건너뛸 수 있는 칸의 개수가 k이내라는 건 건너뛰는 징검다리의 개수가 k-1개 이내라는 걸 놓치면 안됩니다.

이는 문제에서 제시된 예시 그림을 보시면 이해가 쉽습니다.

 

건너뛸 때마다 jump라는 건너뛴 징검다리 수를 증가시키고, 이게 k-1을 넘어버리면 건너지 못한다고 false를 리턴해요.

k-1개 이내로 jump하려는 와중에 건널 수 있는 다리를 만나면 jump를 다시 0으로 초기화해야 합니다.

 

[풀이 후기]

아직 배울 게 많은 초보이기도 하지만 힌트 얻고도 이해하기 어려웠습니다. ㅎㅎ

특히 니니즈 친구들의 수가 무한대라는 말 때문에 이분탐색인지도, 그 범위를 잡는 것도 헷갈렸어요.

건너는 칸 수와 건너는 징검다리의 개수가 다르다는 것도 알아야 했던...어려운 문제였습니다. 

 

풀이 중에 이해가 안되는 부분이나 수정이 필요한 부분은 댓글 달아주세요. 읽어주셔서 감사합니다 :D