[프로그래머스] 징검다리 건너기

카테고리

이분 탐색

나만의 카테고리

이분 탐색

문제 링크

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

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

요점

• 이분 탐색을 구현할 수 있는지를 확인하는 문제
• 개인적으로 5만번 이상의 반복을 시키는 문제는 드물다고 생각 => 그 이상이라면 다른 방법을 찾아야한다
• 이분 탐색 문제의 Target 수가 없고 최대값을 찾는 문제라면 보통 배열 기준이 아닌 문제의 정답에 기준을 맞춰야한다.

참고 지식

• 대개 이분탐색의 Target이 정해져 있다면 탐색의 끝은 mid == target, 아니라면 min > max 일 때 끝이다

풀이 (Java)

class Solution {
    private int min = Integer.MAX_VALUE;
    private int max = Integer.MIN_VALUE;
    
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        findMinAndMax(stones);
        
        while(true) {
            if (min > max) return answer;
            
            int mid = (min + max) / 2;
            
            if(isSuccess(stones, k, mid)) {
                min = mid + 1;
                answer = Math.max(answer, mid);
            } else {
                max = mid - 1;
            }
        }
    }
    
    private boolean isSuccess(int[] stones, int k, int mid) {
        int zeroCount = 0;
        
        for (int stone : stones) {
            // 0의 연속 찾기
            if (stone < mid) {
                zeroCount++;
            } else {
                zeroCount = 0;
            }
            
            if (zeroCount == k) {
                return false;
            }
        }
        
        return true;
    }
    
    private void findMinAndMax(int[] stones) {
        for (int stone : stones) {
            if (min > stone) min = stone;
            if (max < stone) max = stone;
        }
    }
}

처음에는 너무 쉬운거 아닌가 생각하고 for문으로 전체 배열을 1씩 감소시키며 0이 되는 stone의 연속을 찾았습니다.

하지만 반복을 해야하는 양이 너무 많았고 당연히 효율성에서 실패했습니다.

 

그래서 이분 탐색 문제라고 생각했고 이분 탐색을 이용할 때는 배열을 기준으로 생각하기 보다는 통과해야하는 점수나 이번 문제에서는 <최대 몇 명>에 기준을 맞춰 푸는 경우가 많은것 같습니다.

 

따라서 n명이 통과를 할 수 있냐 없냐를 판단하여 정답을 찾아내는게 요점인 문제였습니다.

---

 

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!