[프로그래머스/2019 카카오 개발자 겨울 인턴십/Java & python] 징검다리 건너기

3차례에 걸쳐....

완성된 코드...

 

로직

실패한 코드라 의미없을 수도 있겠지만 간단하게 말하면, 

전체 리스트에서 k 만큼의 길이로 쪼개 만들어진 리스트를 subList라고 가정하자

예를 들어, { 2, 4, 5, 6, 2, 1, 4, 2 } 라는 전체 리스트가 주어지고 k = 3이라고 가정하면 subList는 {2, 4, 5}, {4, 5, 6}, {5, 6, 2}, ... 이 된다.

그리고 각 subList에서 max값을 찾고, 그렇게 구한 subList max값들 중 가장 작은 값을 선택한다.

가장 작은 값이 곧 최종적인 리턴값이 된다.

 

설명하기 좀 복잡해서 자세한건 나중에 (아이패드로 설명하자)

아무튼 선형탐색이라서 O(n^2)이 걸린다. 테스트 케이스 모두 돌아가는데 정확도 테스트 13번이라는 산을 넘지 못했따...

코드 #1 실패

class Solution {
    public int solution(int[] stones, int k) {
        int maxIndex = -1;
        int minSublist = Integer.MAX_VALUE;
        
        for(int start = 0; start <= stones.length - k; start++){
            if(maxIndex < start){
                maxIndex = getMaxFromWhole(start, k, stones);
            } else {
                int next = start + k - 1;
                if(stones[next] >= stones[maxIndex]) maxIndex = next;
            }
            minSublist = Math.min(minSublist, stones[maxIndex]);
        }
        
        return minSublist;
    }
    

    public int getMaxFromWhole(int start, int k, int[] stones){
        int max = 0;
        int maxIndex = -1;
        for(int i = start; i < start + k; i++){
            if(stones[i] > max) {
                max = stones[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

로직

이번에는 여러 다른 사이트들에서 아이디어를 얻은 결과... 이진탐색으로 접근을 해보았다.

mid 값을 기준으로 하여 이진탐색을 하고 적절한 mid값을 찾은 뒤 리턴한다.

 

 

근데 실패했다.

코드 #2 - 1 실패

class Solution {
    public int solution(int[] stones, int k) {
        
        // get initial min and max - n times
        int[] minmax = getMinMax(stones);
        int min = minmax[0], max = minmax[1];
        int mid = (int)(min + max)/2;
        int maxSkips = 0;
        
        // binary search
        // stop when min == max
        while(min <= max){
            mid = (int) (min + max) / 2;
            System.out.println(mid);
            if(search(stones, mid, k)){
                max = mid - 1;
            } else{
                min = mid + 1;
            }
        }
        return min;
    }
    
    public boolean search(int[] stones, int mid, int k){
        int continuousSkips = 0;
        for(int stone : stones){
            if(stone <= mid) continuousSkips++;
            else continuousSkips = 0;
            
            if(continuousSkips >= k)
                return true;

        }
        return false;
    }
    
    public int[] getMinMax(int[] stones){
        int min = 200000000, max = 1;
        for(int stone : stones){
            if(stone < min) min = stone;
            else if(stone > max) max = stone;   
        }
        int[] minmax = {min, max};
        return minmax;
    }
}

 

#2 - 1이 실패한 이유는 맨 처음 min max값을 O(n) 시간을 들여가며 직접 구해주었기 때문에..ㅠ

min max를 그냥 input 최대 최솟값으로 설정하고 설마설마하는 마음으로 돌리니 돌아가더라...ㅎ 오늘도 삽질 성공..!!

코드 #2 - 2 성공

class Solution {
    public int solution(int[] stones, int k) {
        
        int min = 1, max = 200000000;
        int mid = (int)(min + max)/2;
        int maxSkips = 0;
        
        // binary search
        while(min <= max){
            mid = (int) (min + max) / 2;
            if(search(stones, mid, k)){
                max = mid - 1;
            } else{
                min = mid + 1;
            }
        }
        return min;
    }
    
    public boolean search(int[] stones, int mid, int k){
        int continuousSkips = 0;
        for(int stone : stones){
            if(stone <= mid) continuousSkips++;
            else continuousSkips = 0;
            
            if(continuousSkips >= k)
                return true;
        }
        return false;
    }
}

 

코드# 2- 2 python 버전

import math
def solution(stones, k):
    answer = 0
    _max = max(stones)
    _min = 0

    while _min < _max: # min_k == max_k 일 때 종료
        _mid = math.floor((_max + _min) / 2)
        if is_possible(stones, k, _mid):
            _min = _mid
        else:
            _max = _mid - 1
            
    return _min + 1

def is_possible(stones, k, _mid):
    max_cnt = 0
    local_cnt = 0 # 연속적으로 0 이하가 나오는 구간을 카운트
    for stone in stones:
        if (stone - _mid) > 0:
            if local_cnt > 0:
                max_cnt = max(local_cnt, max_cnt)
                local_cnt = 0
        else:
            local_cnt += 1
            if local_cnt >= k: return False
    return True