정확성 테스트만 통과한 코드

• 디딤돌 숫자의 최소값 만큼은 모두 지날 수 있기 때문에 최소값을 구해서 모든 디딤돌에서 빼준다.
• 각 디딤돌을 건너는 상황을 반복문을 통해 구현한다.
• 건너는 상황을 모두 수행하게 되니 시간 복잡도가 매우 높게 나온다.

package kakao.intern2019;

import java.util.*;

// 징검다리 건너기
public class Q4 {
    public static void main(String[] args) {
        int[] stones = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
        int k = 3;
        System.out.println("solution = " + solution(stones, k));
    }

    public static int solution(int[] stones, int k) {
        int answer = 0;
        ArrayList<Integer> stoneList = new ArrayList<>();
        for (int val : stones) {
            stoneList.add(val);
        }
        //최소 값 구하기
        Integer min = Integer.MAX_VALUE;
        for (Integer val : stoneList) {
            if (val < min) {
                min = val;
            }
        }
        // 최소 값 만큼의 사람은 무조건 지나감
        for (int i = 0; i < stoneList.size(); i++) {
            stoneList.set(i, stoneList.get(i) - min);
        }
        answer += min;
        System.out.println("min = " + min);
        System.out.println("stoneList = " + stoneList);
        int stopFlag = 0;
        while (true) {
            // 연속해서 0인 디딤돌의 수
            int cnt = 0;
            for (int i = 0; i < stoneList.size(); i++) {
                Integer cur = stoneList.get(i);
                if (cur > 0) {
                    cnt = 0;
                    stoneList.set(i, cur - 1);
                } else if (cur.equals(0)) {
                    cnt++;
                }
                if (cnt == k) {
                    stopFlag = 1;
                    break;
                }
            }
            if (stopFlag != 0) {
                break;
            }
            answer++;
            System.out.println("stoneList = " + stoneList);
        }
        return answer;
    }
}

이분 탐색(Binary Search)

• 이분 탐색은 정렬된 배열을 상대로 탐색 시간을 O(log) 까지 줄일 수 있다.
• 이 문제의 요점은 결국 몇명의 사람이 건널 수 있냐는 것이다. 즉, 건널 수 있다는 사람이 무제한 이라는 말은 함정이고 0명 ~ [디딤돌의 최대 수]명이 값인 배열에서 조건에 만족하는 수 중 최대값을 찾는 문제라고 할 수 있다. 조건 = [디딤돌 수] - [건넌 사람의 수] ≤ 0 를 만족하는 디딤돌이 k 보다 적음

public static int solution(int[] stones, int k) {
        int answer = 0;
        // 건널 수 있는 사람이라는 가상의 배열이 있다고 생각하고 이진탐색
        // Binary Search start, end value
        System.out.println("stones = " + Arrays.toString(stones));
        int start = 0;
        int end = Integer.MIN_VALUE;
        for (int stone : stones) {
            if (stone > end) {
                end = stone;
            }
        }
        System.out.println("start = " + start);
        System.out.println("end = " + end);

        while (start <= end) {
            int mid = (end + start) / 2;
            System.out.println("mid = " + mid);
            int cnt = 0;
            for (int stone : stones) {
                if (stone <= mid) {
                    cnt++;
                } else {
                    cnt = 0;
                }
                if (cnt >= k) {
                    break;
                }
            }
            if (cnt >= k) {
                // mid명 의 사람이 건너고 나서부터 다음 사람은 건널 수 없는 상황
                answer = mid;
                end = mid - 1;
            } else {
                // start명 보다 적은 사람은 건너는게 보장
                start = mid + 1;
            }
        }
        return answer;

• 왜 answer이 mid 여야 하는지?? 파악하기

  → 조건이 잘못되어있었다. stone 값과 mid 값이 동일하면 건널 수 있는 상황이므로 cnt 값을 증가시키면 안된다.

  for (int stone : stones) {
                  if (stone < mid) {
                      cnt++;
                  } ...
              }
              if (cnt >= k) {
                  // mid명 의 사람이 건너고 나서부터 다음 사람은 건널 수 없는 상황
                  end = mid - 1;
              } else {
                  // start명 보다 적은 사람은 건너는게 보장
  								answer = mid;
                  start = mid + 1;
              }
  

  이렇게 작성해야 생각한 로직과 동일한 결과를 얻을 수 있다.