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

프로그래머스 징검다리 건너기 문제는 카카오 인턴쉽 기출 문제로, 징검다리를 최대 몇명이 건널 수 있는지 구하는 문제다. 난이도는 레벨3이며 이분탐색을 통해 해결할 수 있다.

 

프로그래머스 - 징검다리 건너기 문제 정보

알고리즘 분류

- 이진탐색

- 슬라이딩 윈도우

난이도

- Level 3

 

문제 요약

• 일렬로 놓여있는 징검다리의 디딤돌에는 각각 숫자가 적혀있으며, 한번 밟을 때마다 1씩 줄어듦
  • 디딤돌의 숫자가 0이 되면 더이상 밟을 수 없으며, 가능한 다음 디딤돌로 건너 뛸 수 있음
  • 밟을 수 있는 디딤돌이 여러개인 경우 무조건 가장 가까운 디딤돌로 가야 함
• 한번에 한명씩 징검다리를 건너는데, 한명이 다 건넌 뒤에 다음 사람 건넘
• Q. 징검다리 각 디딤돌의 숫자 및 한번에 건너뛸 수 있는 최대 칸수 k가 주어졌을 때, 최대 몇명까지 건널 수 있는가?

 

문제 풀이 과정 1

• 한 명 지나갈 때 → 양수인 디딤돌의 숫자 무조건 1씩 줄어듦 (밟을 수 있는 디딤돌 못 건너 뜀)
• 사람 0번, 1번, 2번, … 이렇게 지나간다고 가정할 때
  • (디딤돌 수) - (사람 번호) < 0 인 경우가 연속으로 k번 이상인 경우면 못 건넘
• k 사이즈로 슬라이딩 윈도우
  • 윈도우 내의 최대값까지 건널 수 있음
  • 윈도우 최대값의 최소값을 구하면 정답

코드

class Solution {
    public int solution(int[] stones, int k) {
        int answer = Integer.MAX_VALUE;
        int lastMax = answer, lastIdx = -1;
        
        // k 사이즈의 슬라이딩 윈도우
        for(int l=0; l <= stones.length - k; l++) {
            int r = l + k - 1;
            int localMax, localMaxIdx;
            
            // 최대값이 범위를 벗어난 경우 다시 최대값 구함 (O(k))
            if (lastIdx < l) {
                localMax = 0; localMaxIdx = l;
                for(int i = l; i <= r; i++) {
                    int newVal = stones[i];
                    if (newVal >= localMax) {
                        localMax = newVal;
                        localMaxIdx = i;
                    }
                }
            } else { // 최대값이 아직 범위 내에 있는 경우 새로 추가된 값과 비교
                int newVal = stones[r];
                if (newVal >= lastMax) {
                    localMax = newVal;
                    localMaxIdx = r;
                } else {
                    localMax = lastMax;
                    localMaxIdx = lastIdx;
                }
            }
            
            // 현재 윈도우의 최대값으로 갱신
            lastMax = localMax;
            lastIdx = localMaxIdx;
            answer = Integer.min(answer, localMax);
        }
        
        return answer;
    }
}

• 시간복잡도: 최고 O(N), 최악 O(Nk)
  • 효율성 13번이 최악의 케이스(역순 정렬된 경우)라서 해당 케이스만 실패함
  • → 일단 꼼수 써서 문제는 통과함 (13번 케이스만 reverse해서 풂)
• 공간복잡도: O(1)

 

문제 풀이 과정 2

• 사람 0번, 1번, 2번, … 이렇게 지나간다고 가정할 때
  • (디딤돌 수) - (사람 번호) < 0 인 경우가 연속으로 k번 이상인 경우면 못 건넘
  → 가능한 답인 0~200,000,000 중에서 못건너게 되는 지점을 찾아야 함
  • M번까지 건널 수 있는 경우 → 1~M번 건널 수 있음. M+1~ 건널 수 없음
  → 이진탐색으로 건널 수 있는 최대 번호를 구할 수 있음

코드

class Solution {
    public int solution(int[] stones, int k) {
        int answer = bs(stones, 0, 200000001, k);
        return canCross(stones, answer, k)? answer : answer-1;
    }
    
    // 중간번호가 건널 수 있으면 오른쪽, 건널 수 없으면 왼쪽 탐색
    private int bs(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return l;
        }
        
        int mid = (l + r) / 2;
        if (canCross(arr, mid, k)) {
            return bs(arr, mid+1, r, k);
        } else {
            return bs(arr, l, mid-1, k);
        }
    }
    
    // M번이 건널 수 있는지 확인
    // M-1번까지 건넌 상태에서 0이하값이 연속으로 k개 이상 나오는지 확인
    private boolean canCross(int[] stones, int M, int k) {
        int zeroCnt = 0;
        for (int i = 0; i < stones.length; i++) {
            if (stones[i] - (M - 1) <= 0) {
                zeroCnt++;
                if (zeroCnt >= k) {
                    return false;
                }
            } else {
                zeroCnt = 0;
            }
        }
        return true;
    }
}

• 시간복잡도: O(NlogM) … N: 디딤돌 개수, M: 디딤돌 숫자 최댓값(200,000,000)
  • 1번 풀이보다 안정적인 시간 복잡도를 가짐. 최악의 케이스에도 통과 가능.
• 공간복잡도: O(logM) … 재귀함수 스택