Today I Learned

오늘은 프로그래머스에서 lv.3 랜덤 문제를 풀어보았다.

징검다리 건너기

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

문제

징검다리 배열이 주어진다. 징검다리에서 각 디딤돌은 최대로 건널 수 있는 횟수가 적혀있다. 빈 디딤돌을 연속으로 점프할 수 있는 최대 횟수 k 가 주어진다. 이때 최대로 건널 수 있는 사람의 수를 구하라.

구현 과정

• 구현 자체는 난이도가 높지 않은데 효율성테스트에서 계속 실패해 접근 방식을 여러번 바꿔서 시도했다.

while문으로 구현 (효율성 실패)

1. 단순 반복문으로 계속 사람 수를 늘려가면서 건널 때 마다 바위의 횟수를 차감하는 식으로 구현했다.

2. 정답은 나왔지만 효율성 측면에서 실패해서 다른 방법을 모색해봤다.

슬라이딩 윈도우 (효율성 실패)

1. k를 슬라이딩윈도우 범위로 두고 k 크기의 부분 배열에서 최대값을 뽑고 그 최대값들 사이에서 최소값을 찾는다면 답이 나온다.

2. 하지만 자바 코드로는 큐처럼 맨 앞의 값을 제거하고 맨 뒤에 값을 넣으면서 최대값을 동시에 찾는 효율적인 자료구조가 없었다.

3. 그래서 큐를 가지고 최대값을 찾는 비효율을 안고 시도 했더니 역시 효율성 테스트에 실패했다.

4. 약간의 수정만 있으면 이 방법이 가장 빠를 것 같은데 나중에 좀 더 생각해봐야겠다.

이분탐색

1. 특정 인원으로 다리를 건너는 것이 가능한지에 대한 boolean 메서드를 하나 만든다. stone이 n보다 작으면 카운트를 늘리고, n보다 크면 카운트를 0으로 다시 초기화해서 연속 카운트가 몇개인지 판단해 k와 비교한다.

2. 이분탐색으로 위에서 구현한 isPossible 메서드를 실행시킨다. mid값을 구한 뒤, isPossible이 통과 되면 min을 mid+1로 올리고, 통과가 안되면 max를 mid-1로 내려서 최대의 mid 값을 찾는다.

Java 코드

while 코드

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        int ans = 0;
        int n = stones.length;
        boolean flag = true;
        int c = 0;
        while(flag){
            for(int i=0; i<n; i++){
                if(stones[i] > 0){
                    stones[i]--;
                    c = 0;
                } else {
                    c++;
                    if(c>=k) return ans;
                }
            }
            ans++;
        }
        return ans;
    }
}

슬라이딩 윈도우 코드

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        int l = stones.length;
        int right = k-1;
        int max = 0;
        
        Queue<Integer> q = new ArrayDeque<>();
        for(int i=0; i<k;i++){
            q.add(stones[i]);
            max = Math.max(max, stones[i]);
        }
        int min = max;
        
        for(int left = 1; left<l-k; left++){
            right++;
            int a = q.poll();
            q.add(stones[right]);
            if(a==max){
                Integer[] b = q.toArray(new Integer[0]);
                for(Integer bb : b){
                    max = Math.max(max,bb);
                }
            } else{
                max = Math.max(max, stones[right]);
            }
            
            min = Math.min(min, max);
        }
        
        
        return min;
    }
}

이분탐색 코드

import java.util.*;
class Solution {
    boolean isPossible(int n, int k, int[] stones){
        int count = 0;
        for(int stone : stones){
            if(stone<n){
                count++;
                if(count>=k) return false;
            } else {
                count = 0;
            }
        }
        
        return true;
    }
    
    
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        int min = 1;
        int max = 200000000;
        
        while(min<=max){
            int mid = (min+max)/2;
            
            if(isPossible(mid,k,stones)){
                min = mid+1;
                answer = Math.max(answer, mid);
            } else {
                max = mid-1;
            }
        }
        return answer;
    }
}