Programmers - 징검다리 건너기 with JAVA (V)

 

 

문제

징검다리의 칸마다 건널 수 있는 횟수가 정해져 주어지고 사람이 건너 뛸 수 있는 칸의 수가 주어진다. 이 때, 최대한 많은 사람들이 건너게 하고자 할 때, 최대 몇명이 건널 수 있는가?

 

 

로직

이 문제에 대해서 많은 고찰이 있었다.

시간 복작도를 충분히 고려해야하는 문제이다.

 

첫번째 생각했던 방법은 0~k, 1~k+1마다 최댓값을 구하고 이 최댓값들 사이의 최솟값이 정답이 되는 로직을 설정하였다.

이는 시간복잡도에서 큰 문제를 갖는데 매 순간 정렬을 해줘야 하기에 문제가 생긴다.

 

따라서, 이분탐색으로 해결을 하였다.

1. 주어진 배열 정렬해 리스트에 담는다.

2. 이분 탐색으로 숫자를 정해가며 해당 리스트에서 지금 값을 뺐을 때, k보다 작거나 같거나 크거나를 고려하여 start, end 인덱스를 변경해가며 답을 찾는다.

 

 

코드1

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        int answer = (int)1e9;
        List<Integer> new_stones = new ArrayList<>();
        for(int stone : stones){
            new_stones.add(stone);
        }
        Collections.sort(new_stones);
        int start = 0;
        int end = new_stones.size()-1;
        while(true){
            if(start > end){
                break;
            }
            int mid = (start+end)/2;
            int value = new_stones.get(mid);
            int count = 0;
            int result = 0;
            for(int stone : stones){
                if(stone - value > 0){
                    result = Math.max(result, count);
                    count = 0;
                    continue;
                }
                count += 1;
            }
            result = Math.max(result, count);
            if(result < k){
                start = mid+1;
            }
            else{
                end = mid-1;
                answer = Math.min(answer, value);
            }
        }
        return answer;
    }
}

 

 

코드2

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        List<Integer> new_stones = new ArrayList<>();
        for(int stone : stones){
            new_stones.add(stone);
        }
        Collections.sort(new_stones);
        int start = 0;
        int end = new_stones.size()-1;
        int answer = new_stones.get(end);
        while(start <= end){
            int mid = (start+end)/2;
            int value = new_stones.get(mid);
            int result = 0;
            int count = 0;
            for(int stone : stones){
                if(stone-value <= 0){
                    count += 1;
                }
                else{
                    count = 0;
                }
                result = Math.max(result, count);
            }
            if(result < k){
                start = mid+1;
            }
            else{
                answer = Math.min(answer, value);
                end = mid-1;
            }
        }
        return answer;
    }
}

 

실수 : 해당 코드에서 result = Math.max(result, count)를 else안에 작성을 하였는데 해당 경우에는 정확한 result값을 구하지 못할경우가 생김.