프로그래머스 레벨3 - 카카오 2019인턴 징검다리건너기

문제주소

programmers.co.kr/learn/courses/30/lessons/64062

내 풀이

def solution(stones, k):
    if k == 1:
        return min(stones)
    # k가 1이 아닌 경우
    answer = binary_search(k, stones, 1, max(stones))
    return answer


def is_cross(stones, answer, k):
    start = 0
    end = 0
    for i in range(1, len(stones)):
        if stones[i] <= answer:
            end = i
            if stones[i - 1] > answer:
                start = i
        if end - start == k - 1:
            return False
    return True


def binary_search(k, stones, start, end):
    if start == end:
        if is_cross(stones, start, k):
            return start + 1
        return start
    mid = (start + end) // 2
    if is_cross(stones, mid, k):
        return binary_search(k, stones, mid + 1, end)
    return binary_search(k, stones, start, mid)

처음에 효율성이 걸려있어서 start, end를 사용하여 투포인터를 사용하는 문제인가 싶었다. 하지만 포인트는 그게 아니라.. 이분탐색..ㅎㅎ

 

효율성문제를 어떻게 해결하는지 몰라서 카카오 tech 힌트를 봤다. -> 이분탐색을 사용해라!

이분탐색.. 어려워서 코딩테스트 책을 보면서 하나하나 구현해 보았다.

 

이분탐색에서 중요한 것은 탐색조건과 종료조건이다. 특히 재귀를 구현하는 것은 종료조건이 가장 중요하다. 대소비교(start>end)로 종료조건을 할 경우는 end = mid + 1로 해도 된다. 하지만, 나같은 경우는 == 조건으로 종료조건을 설정하였다. 따라서 비는 start > end가 되는 경우가 없이 탐색되는 것이 중요하다. 

 

이분탐색을 생각하기 어려웠던 것은 어떤 값을 기준으로 이분탐색을 할 것인지였다. 건널수 있는 친구의 수가 무한대이므로 stones의 값에서 가장 큰 값 동안 밟을 수 있다. 정답이 될 수 있는 가장 큰 값과 최솟값을 찾아 start, end로 넣고 이분탐색을 하면 된다. 따라서 조건에 따라서 가장 큰 값은 max(stones), 최솟값은 1이 된다. 이것을 기준으로 이분탐색을 통해 값을 도출해냈다.

다른 사람 풀이

효율성이 걸렸기 때문에 이분탐색을 사용했고, 재귀로 구현하는지 while로 구현하는지 차이였다.

 

건널수 있는 조건을 따지는 풀이가 좀 달랐다.

방법 1 : temp = mid 으로 설정해서 mid 값 보다 작은경우 -1을 해주고 temp ==0 이 되면 False를 리턴해주는 풀이가 있었다. -> 간단하고 빠른듯 하다.

방법 2 : mid 값을 기준으로 0설정을 다시 해주고, 0보다 작은경우만 temp +=1을 해주고 gap = max(gap, temp)로 한 풀이도 있었다.

 

정리 

이분탐색 공부를 해야겠다는 생각이 들었다. 스스로 구현할 수 있는 실력이 되어야지! 이분탐색 문제를 몇 개 더 풀어봐야겠다. 😀