[programmers] 징검다리 건너기 (Java)

[징검다리 건너기]

코딩테스트 연습 - 2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기

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

프로그래머스

 

[접근 방식]

단순히 문제의 흐름에 따른 방식은 반드시 시간 초과에 맞닥드려 해결할 수 없다.

이진 탐색을 사용하여 문제를 해결해야 한다.

[Java 코드]

[효율성 테스트 실패 - 시간 초과]

//https://school.programmers.co.kr/learn/courses/30/lessons/64062
//코딩테스트 연습 - 2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기


class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;

        for (int member = 1; member <= Integer.MAX_VALUE; member++) {
        
            int jump = 1;
            for (int i = 0; i < stones.length; i++) {
                if (stones[i] == 0) {
                    jump ++;
                } else {
                    stones[i] --;
                    jump = 1;
                }

                if (jump > k) {
                    return answer;
                }
            }
            answer++;

        }

        return answer;
    }
}

 

[이진 탐색을 이용한 코드 - 성공!]

//https://school.programmers.co.kr/learn/courses/30/lessons/64062
//코딩테스트 연습 - 2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기


class Solution {
    public int solution(int[] stones, int k) {

        //left : 징검다리를 건널 수 있는 사람의 최솟값
        //right : 징검다리를 건널 수 있는 사람의 최댓값
        int left = 1; 
        int right = Integer.MIN_VALUE;

        // left / right 초기화
        for (int stone : stones) {
            if (stone > right) {
                right = stone;
            }
        }

        //이진 탐색으로 범위 줄이기
        while (left <= right) {
            int mid = (left + right) / 2;
            if (skip(stones, k, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return right;
    }

    // 징검다리를 건널 수 있는지 판단하는 메서드
    private boolean skip (int[] stones, int k, int mid) {
        int skip_stone = 0;
        for (int stone : stones) {
            if (stone - mid < 0) {
                skip_stone ++;
                if (skip_stone >= k) {
                    return false;
                }
            } else {
                skip_stone = 0;
            }
        }
        return true;
    }

}

 

[Rewind]

1. 어려웠던 점

- 이진 탐색으로 해결하는 방법을 생각해내는 것이 어려웠다.

- 문제 해결 아이디어에 도달하지 조차 못하는 것에 무력감을 느낀다.

 

2. 알게된 점

- 이진탐색을 활용하는 문제를 하나 더 접한 것에 의의가 있다.

 

3. 개선 방안

- 문제의 해결방식에 전혀 도달하지 못하는 것은 심각한 문제이다.

- 같은 해결방식을 사용하는 문제를 여러개 접한 후에도 해당 해결방식을 생각해내지 못하는 것은 심각한 문제이다.

- 이진 탐색을 활용하는 다른 문제를 풀 것인데, 이진 탐색을 사용하는 것임을 알고도 문제를 해결하지 못한다면, 이는 심각한 문제로서 더 이상 Problem Solving 을 지속할 이유가 없다.