[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기 (java)

문제설명

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

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

[제한사항]

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

---

문제접근

알고리즘풀이 시, 제한사항을 참고하여 어떤 방향으로 문제를 접근할 지 생각하는 것은 중요합니다.

제한사항을 보면 알 수 있듯이 한 돌이 밟힘의 허용치가 최대 200,000,000 입니다. 그런돌이 200,000이 있으므로

니니즈 친구들을 한 명씩 보내면서 통과하면 answer++ 를 하기에는 범위가 무척 큽니다.

 

이와 비슷한 문제를 기존에 풀어서, 쉽게 풀이했습니다.

https://in-intuition.tistory.com/21?category=935259

[프로그래머스] 징검다리(Java) [이분탐색]

https://in-intuition.tistory.com/17?category=935259

[프로그래머스] 입국심사 java [이분탐색]

 

이분탐색을 이용하여 풀이하였습니다.

 

• left 값을 몇으로 잡아야 하나? 
  • stonse 원소의 최솟값인 1 로 잡았습니다.
• right 값을 몇으로 잡아야 하나?
  • stonse 원소의 최대값인 200,000,000 로 잡았습니다.
• mid = (left+right)/2    //  mid = left+right/2   로 풀다가 while문을 빠져나오지 못해서 잠깐 당황했었습니다.. ㅜㅜ
• stonse 배열을 순회하며 stonse[i]-mid 가 0보다 작다면 현재 바위에서부터 건너 뛴 횟수를 세어줍니다. 
  • 건너 뛴 횟수가 k 와 같거나 크다면 mid값에 해당하는 니니즈 친구들이 너무 많은 것입니다.
  • 그러므로 해당 mid값에서의 더 이상의 순회는 필요없으므로 반복문을 나가도됩니다.
  • right= mid-1
• 만약 stonse 배열을 모두 순회하여 조건을 만족한다면 answer이 될 가능성이있습니다.
  • 하지만 최대의 answer은 아닐 수 있으므로 left = mid+1 이 됩니다
  • answer = answer > mid ? answer:mid 

코드

public int binarySearch(int[] stones, int k){
    int left=1;
    int right=200000000;
    int mid=0;
    int answer =0;

    while(left <= right){
        mid=(left+right)/2;
        System.out.println(mid);
        int cnt=0;
        boolean isPossible=true;
        for(int i=0; i<stones.length; i++){
            int now = stones[i];
            now-=mid;
            if(now>=0){cnt=0;}
            else if(now<0){ cnt++;}
            if(cnt>=k){isPossible=false; break;}
        }
        if(isPossible==false){
            right=mid-1;
        }
        else{
            left=mid+1;
            answer = answer>mid ? answer:mid;
        }
    }

    return answer;
}

깃허브 : https://github.com/jsh9057/Algorithm/blob/master/src/KakaoWinter/SteppingStone.java 

jsh9057/Algorithm