2019 KAKAO WINTER INTERNSHIP - 징검다리 건너기

저는 신기하게 KAKAO 문제만 보면 왜 이렇게 지레 겁부터 먹고 시작할까요?

 

이번 문제가 딱 그렇습니다.

 

정말 수 없이 풀어봤을 문제 유형인데..

 

KAKAO 라서 그런지 생각이 잘 안떠오르네요.

 

유형만 체크되면, 5분만에 풀 수 있었던 문제였는데, 말이죠 ?

 

본인의 실력을 믿고 푸는 마음가짐이 필요해보입니다 !

 

---

이 문제의 경우 제가 치뤘던 겨울 인턴십 코딩테스트에서 풀지 못했던 문제였는데, 지금도 마찬가지네요.

 

결국엔 '이진 탐색' 키워드를 보고 문제를 풀었지만, 키워드를 머릿 속에서 떠올려야 진정한 실력이 될 수 있겠죠?

 

앞서 말했듯이 이 문제는 이진 탐색 문제입니다.

 

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

코딩테스트 연습 - 징검다리 건너기

범위가 200,000 / 200,000,000 숫자가 등장하면서 이 문제는 심상치 않음을 알 수 있죠 !

 

그렇기에 막무가내 브루트 포스가 아닌 어떠한 알고리즘 / 개념을 사용해야 풀 수 있는 문제임을 알 수 있습니다.

 

저는 어떤 개념을 사용해야하는지 떠오르지 못해서 결국 키워드를 봤지만 여러분은 다를거라고 생각합니다 ㅎㅅㅎ;;

 

앞서 말했다시피 이 문제는 이분 탐색으로 몇 명의 친구가 길을 건널 수 있을지를 범위 잡아서 찾아가면 됩니다.

 

그 인원이 길을 건널 수 있는지 없는지를 판단하는 chk 함수는 0의 돌을 지날 때마다 카운트를 해주어서 k의 값 이상이면 그 인원은 건널 수 없으니 인원을 더 줄여가면서 체크를 하면되고, 건널 수 있으면 인원을 좀 더 늘려가면서 정답을 찾으면 되겠죠?

answer = [0]

def chk(mid, stones, k):
    temp = [x - mid if x - mid > 0 else 0 for x in stones]
    cnt = 0
    for t in temp:
        if t == 0:
            cnt += 1
            if cnt >= k:
                return False
        else:
            cnt = 0
    return True

def bsearch(s, e, stones, k):
    if (s > e):
        return
    mid = (s + e) // 2
    if chk(mid, stones, k):
        answer[0] = mid
        bsearch(mid + 1, e, stones, k)
    else:
        bsearch(s , mid - 1, stones, k)

def solution(stones, k):
    l = 0; r = max(stones)
    bsearch(l, r, stones, k)
    return answer[0] + 1

---

이상 2019 KAKAO WINTER INTERNSHIP - 징검다리 건너기였습니다. ^_^