[python] 징검다리 건너기 (2019 카카오 개발자 겨울 인턴십)

[한줄평]

정확성과 더불어 효율성을 요구하는 문제는 대비할 수 있는 풀이들이 많다. hash나 이분 탐색 등.. 꼭 생각을 할 수 있어야 한다.

 

[풀이]

0. 문제를 풀기 전 한 생각

직관적으로 봤을 때 전체 탐색을 하면 정확성은 만족 할 수 있을 것 같지만, 효율성을 요구하는 문제이므로 당연하게도(?) 전체 탐색을 하면 안 될 것 같다. (전체 탐색 + DP로 안될 것 같은 문제는 이분 탐색을 사용하면 NlonN까지 시간 복잡도를 줄일 수 있다는 것을 알고 있으므로 이분 탐색을 어떻게 해야될까? 라는 생각을 하면서 ...) 게다가 '최대'로 건널 수 있는 사람의 수를 구하라고 했기 때문에, 사람 수를 이용할 수 있지 않을까? 라는 생각을 하였다.

 

1. 사람 수를 기준으로 이분 탐색을 진행 할 것이므로, 초기 left값 (제일 작은 사람 수)는 0명, 초기 right값 (제일 많은 사람 수)는 돌다리의 가장 큰 수인 200000000으로 설정하였다. k개 이상의 징검다리를 건널 경우가 답을 내기 위해 꼭 고려해줘야 할 조건이기 때문에 징검다리의 개수를 셀 변수인 gap도 만들어준다.

2. 이분 탐색의 특성 상, left가 right보다 커질 수 없으므로, left <= right 조건 안에서 코드를 진행한다.

3. mid값은 결국엔 target값, 즉 전체 건널 수 있는 사람 수 가 될 수 있기 때문에, 전체 건널 수 있는 사람의 수보다 디딤돌 수(높이?)가 작아질 수 없다. 그러므로 조건을 디딤돌 수 (stone)과 건널 수 있는 사람 수 (mid)의 대소 비교를 통해 조절해준다.

4. 디딤돌 수보다 건널 수 있는 사람의 수가 클 경우에는, 건널수 없는 디딤돌이므로 그 디딤돌은 건너 뛰어야 하므로 gap을 하나씩 늘려준다.  

4-1. 이때 !! 이렇게 건너 뛴 디딤돌의 개수인 gap이 k개가 된다면, 못 건너는 사람이 있다는 의미이므로, 우선 for문을 빠져나가야 한다. 이 때 gap의 값은 실제로는 절대 나올 수 없는 값인 k+len(stones)로 바꿔준다. (나중에 쓰임)

5. 만약 디딤돌 수가 더 클 경우에는, gap을 없애주면 되겠다

6-1. 만약 gap 값이 k+len(stones)라면 못 건너는 사람이 있다는 의미이므로, right값을 mid-1로 줄여준다!

6-2. 이 경우가 아닌 경우는, left값을 mid+1로 늘려주면서 target값을 맞춰주면 된다.

 

끄읕~~

 

다음에도.. 풀 수 있겠찌??? 헿