[프로그래머스] Level 3 : 징검다리 건너기(Java)

문제 링크

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

프로그래머스

---

💡 풀이

 처음 풀이 방식은 stones 배열의 값을 1씩 줄여 나아가면서 건널 수 있는지 확인하는 완전탐색을 이용했습니다. 하지만, 효율성 테스트에서 실패하게 됩니다. 따라서 다음과 같은 방법이 필요합니다.

 

이진 탐색

 이진 탐색을 이용하여 풀이합니다. k의 범위는 1부터 stones의 길이까지이기 때문에, stones의 모든 원소가 0이 된다면, 건널 수 없게 됩니다. 따라서, 0부터 stones 배열의 최대 원소값 사이에서 이진 탐색을 진행해 점프가 가능하다면 그보다 많은 사람 수에 대해 검사하고, 점프가 불가능하다면 그보다 적은 사람의 수에 대해 검사를 진행하며 최종적으로 가능한 최대 명수를 구하는 방식입니다.

 

사람 수에 따른 stones 배열의 변화 저장

 먼저, 건넌 사람의 수에 따라 stones 배열의 변화를 저장해줄 필요가 있습니다. 이 결과를 토대로 건널 수 있는 다리인지 아닌지 확인하게 됩니다. stones 배열과 건넌 사람의 수를 인자로 받는 함수를 만들어 줍시다. 

int[] crossStones(int[] stones, int person) {
    return Arrays.stream(stones)
        .map(value -> value - person)
        .toArray();
}

stones 배열의 각 원소에서 건넌 사람의 수인 person을 뺀 배열을 반환합니다.

 

건널 수 있는 다리인지 확인

 다음은 이 배열을 이용해 건널 수 있는 다리인지 확인하는 함수가 필요합니다.

 0으로 초기화된 jump 변수를 설정합니다. 이 변수는 그냥 건널 수 있는 돌 즉, 0보다 큰 돌을 만나면 0이 되고, 0 이하의 돌을 만나게 되면 1씩 증가합니다.

 예를 들어, [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]인 stones 배열에서 3명이 건너게 되면, 위의 crossStones 함수에 의해 [-1, 1, 2, 0, -1, -2, 1, -1, 2, -2]가 될 것입니다. 이 배열을 탐색하며 jump를 적용시키면, 각 원소에 해당하는 jump는 [1, 0, 0, 1, 2, 3, 0, 1, 0, 1]이 됩니다. 이를 해석하면 연속된 점프의 수가 최대 3이라는 것을 의미합니다. 이 중 가장 큰 jump(여기서는 3)와 주어진 k를 비교해 k가 maxJump보다 크다면, 건널 수 있는 돌다리라는 것을 의미합니다.

boolean canCross(int[] stones, int k) {
    int jump = 0;
    int maxJump = Integer.MIN_VALUE;

    for(int index = 0; index < stones.length; index++) {
        if(stones[index] <= 0) {
            jump++;
        } else {
            jump = 0;
        }
        maxJump = Math.max(maxJump, jump);
    }
    return k > maxJump;
}

 

이진 탐색을 이용해 stones 배열을 탐색

이제 이진 탐색을 이용해 stones 배열에서 최대로 건널 수 있는 사람의 수를 구해봅시다. 먼저 left = 0, right = (stones 배열 원소의 최댓값) 으로 설정하여 탐색을 시작합니다. 만약 중간 값을 검사했을 때, 건널 수 있는 사람의 수라면, left = mid + 1로 설정하여 다시 이진 탐색을 시도하고, 건널 수 없는 사람의 수라면 right = mid - 1로 설정해 이진 탐색을 수행합니다. 이렇게 진행하다가 left가 rigth보다 크게되면, 탐색을 종료하고 저장된 정답을 반환합니다. 

...
int left = 0;
int right = Arrays.stream(stones).max().orElse(0);
int[] newStones = new int[stones.length];

while(left <= right) {
    int mid = (left + right) / 2;
    newStones = crossStones(stones, mid);

    if(canCross(newStones, k)) {
        left = mid + 1;
        answer = mid;
    } else {
        right = mid - 1;
    }
}
...

 

전체 코드

전체적인 코드는 다음과 같습니다.

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 1;
        int left = 0;
        int right = Arrays.stream(stones).max().orElse(0);
        int[] newStones = new int[stones.length];
        
        while(left <= right) {
            int mid = (left + right) / 2;
            newStones = crossStones(stones, mid);
            
            if(canCross(newStones, k)) {
                left = mid + 1;
                answer = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return answer + 1;
    }
    
    int[] crossStones(int[] stones, int person) {
        return Arrays.stream(stones)
            .map(value -> value - person)
            .toArray();
    }
    
    boolean canCross(int[] stones, int k) {
        int jump = 0;
        int maxJump = Integer.MIN_VALUE;
        
        for(int index = 0; index < stones.length; index++) {
            if(stones[index] <= 0) {
                jump++;
            } else {
                jump = 0;
            }
            maxJump = Math.max(maxJump, jump);
        }
        return k > maxJump;
    }
}