[프로그래머스 | Java Lv.3] [2019 카카오 개발자 겨울 인턴십] 징검다리 건너기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/64062?language=java

프로그래머스

---

접근

- 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.

- 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.

- 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

 

첫번째 코드 - 정확성 테스트 o , 효율성 테스트 x (시간 초과)

 

가장 단순하게 풀고 답이 나와서 좋아했지만 역시나 효율성 테스트에서 시간 초과가 떴다. (lv3인데 그럼) 

package week19.baek.september24.baek;

public class P64062 {
    public static int solution(int[] stones, int k) {
        int count = 0;

        while(true){

            int p = 1;
            for (int i = 0; i < stones.length; i++) {

                //돌이 남아있으면 건너기
                if(stones[i] > 0) {
                    stones[i]--;
                    p=1;
                }

                //남아있지 않으면 다음 것을 확인
                else {
                    //더 이상 못 건너면
                    if(p >= k) return count;

                    p++;
                }

            }
            count++;
        }

//        return count;
    }

    public static void main(String[] args) {
        int[] stones =  {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};

        System.out.println(solution(stones, 3));

    }
}

---

이분탐색 문제

 

이분탐색으로 효율적으로 찾아야지만 시간 초과가 나지 않았던 문제이다. 

 

 

징검다리의 내구도가 n일 때, 사람이 한 번씩 건널 때마다 내구도가 1씩 감소하는 과정을 반복하기보다는, 내구도를 미리 n - 3로 한 번에 감소시키고 그 상태에서 징검다리를 건널 수 있는지 확인하는 방법이 동일한 효과를 낸다.

 

--> 일일이 감소시키면서 확인하기 보다는 이분탐색으로 mid 값을 설정하고, mid 값의 사람이 징검다리를 건널 수 있는지를 체크

최종코드

package week19.baek.september24.baek;

// 참고: https://velog.io/@hyeokkr/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC-%EA%B1%B4%EB%84%88%EA%B8%B0-with-Java

public class P64062 {
    public static int solution(int[] stones, int k) {
        int answer = 0;
        int min = 1, max = 200000000;

        while(min<=max) {
            int mid = (min + max) / 2;

            if(isToCross(mid, stones, k)) {
                answer = Math.max(answer, mid);
                min = mid + 1;
            }
            else
                max = mid - 1;
        }

        return answer;
    }

    static boolean isToCross(int mid, int[] arr, int k) {
        int num = 0;

        // 반복문을 돌면서, mid 명의 사람이 건널 수 있는 지 체크
        for(int i : arr) {

            if(i - mid < 0) num++; // 밟지 못하는 칸이 얼만큼 연속되는지 카운트
            else  num = 0;

            //탈출
            if(k == num) // 한 번에 건널 수 있는 칸과 같으면 못 건너는 것
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] stones =  {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};

        System.out.println(solution(stones, 3));

    }
}

 

---

Reference

https://thdbs523.tistory.com/210

[프로그래머스/자바] 징검다리 건너기 풀이 - 2019 카카오 개발자 겨울 인턴십