23.03.16 파이썬 코딩 퀴즈#198 징검다리 건너기 (프로그래머스 스쿨)

이번 문제는 징검다리 건너기 문제이다.

설명이 괴랄한것이 역시 카카오 관련 문제이고, 2019년 카카오 개발자 겨울 인턴쉽 문제였다.

먼저 설정된 규칙을 살펴보자.

징검다리는 일렬로 놓여 있고 각 디딤돌에는 모두 숫자가 적혀있으며, 한 번 밟을 때마다 1씩 줄어든다.

디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때에는 그 다음 디딤돌로 한번에 여러 칸을 건너띌 수 있지만, 무조건 가까운 디딤돌로만 건너띌 수 있다. 하지만 k 값 이상의 거리는 건너 띌 수 없다.

제한 사항에서는 특별하게 없지만, 징검다리를 건너야 할 니니즈의 친구들의 수는 무제한이라고 가정한다.

친절한 그림 설명을 살펴보자. 먼저 첫번째 친구는 모든 디딤돌을 밟고 지나간다

그리고 두번째 친구는 가운데 숫자가 0인 디딤돌이 있지만 k 가 3이기 때문에 2칸은 이동 가능하다.

그 다음 친구는 가운데 숫자가 0인 디딤돌이 2개가 되었지만, 역시 건널 수 있다.

그리고 4번째 친구는 가운데 숫자가 0인 디딤돌이 3개 이기 때문에 더이상 건널 수가 없게된다. 따라서 최대 3명이 징검다리를 모두 건널 수 있다.

 

쉽게 생각하면 굉장히 단순한 문제이다. 전달받은 stones 배열의 값을 1씩 감소시켜 주면서 각 회마다 answer 값을 1 씩 증가시켜 주면된다. 그리고 최종적으로 0의 갯수가 k 가 되는 시점에서의 answer 값을 반환하면 된다.

그리고 그 단순한 생각을 코드로 구현하면 위와 같다.

우선 징검다리를 건널 수 있는지 확인하고, 건널 수 있다면 stones 배열의 모든 요소들을 1 감소 시킨다.

그 다음 answer 값을 증가 시키고, 위 과정을 반복한다.

당연히 효율성 테스트에서 떨어진다.... 단 하나의 효율성 테케는 통과하지 못했다.

 

다음코드... 배열의 각 구간을 k 개수만큼씩 쪼개서 그 배열의 max 값을 answer에 전달하였다.

k가 3이라고 가정하면 [5,3,2] 으로 슬라이싱된 배열이 생성되고, 모든 요소의 값을 0으로 만들기 위해서는 배열의 max()값이 필요한걸 생각하였다. 모든 테케는 통과하였지만, 효율성 테스트는 모두 실패이다....

 

그리고 대망의 마지막 코드.

어짜피 통과 가능한 구간만 확인하면 되기 때문에 전체를 다 탐색할 필요가 없다

이분탐색을 위해 start, finish, mid 3개의 변수를 선언하였다.

그리고 mid 값을 stones 의 요소들에 연산을 적용하였고, 연속적으로 비는 공간을 확인하기 위해 jump 변수를 사용하였다.

만약 k 이상만큼 jump 를 해야한다면 그 뒤로는 통과할수 없기 때문에 break 로 반복문을 종료하여 주고, 그렇게 구한 jump 값을 확인하여 finish 와 start 값을 증감 시켜주면 된다.

 

위 입출력 예를 위 코드에 적용시켜보면 처음 start = 0, finish = 5, 따라서 mid = 2가 된다.

jump 가 k(3) 미만이므로 start 값은 3으로 바뀐다.

다음은 start = 3 , finish = 5, mid = 4 이다.

이때 jump 가 k 이상이므로 finish 값은 3으로 바뀌게 된다.

그 다음은 start = 3, finish = 3, mid = 3 이다.

아직 while문 조건을 충족하므로 이번이 마지막 바퀴가 된다.

이때 jump 가 k 이상이므로 finish 값은 2로 바뀌고, 조건을 충족하지 않기 때문에 while문은 종료된다.

따라서 start 값을 전달해주면 된다.

 

이분탐색법은 찾고자 하는 값과 증감값의 설정, 반복문의 조건 설정에 따라 사용할 값이 달라진다.

예를 들어 위 처럼 조건을 미만으로 잡게되면 finish 는 mid 로 되고, start 는 mid+1 만큼 증가되야 한다.

그 이유는 코드를 직접 작성해 보면 쉽게 알 수 있다.