[프로그래머스] 징검다리 건너기 #python3 #이진탐색 binary search [2019 카카오 개발자 겨울 인턴십]

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

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

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

---

[입출력 예]

stones	k	result
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]	3	3

입출력 예에 대한 설명

---

입출력 예 #1

첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.

첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다. 
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.

풀이

프로그래머스의 문제와 카카오 문제는 스타일이 다릅니다. 프로그래머스 2단계, 3단계 문제는 대부분 문제에서 하라는대로 구현하면 통과하는 경우가 많습니다. 난이도 조절을 위해 3단계에서는 어떻게 구현할 지에 대한 가이드라인이 모호하게 만들어 푸는 방법을 모르겠는 문제가 많습니다.

카카오 문제는 하라는대로 구현하면 틀립니다. 정확히는, 효율성 테스트가 없는 1, 2번 문제 같은 경우에는 하라는대로 하는 문제(대신 노가다성이 짙어 시간을 잡아먹는 문제)가 나오며, 3번 이후로는 문제가 제시하는 방법이 아닌, 더 빠르게 동작할 수 있는 방법을 찾아야 합니다. 위 문제의 경우만 해도 효율성 테스트가 14나 되어 카카오가 정해놓은 '정답' 이외의 풀이로는 운 좋게 한 두개 통과할 순 있어도 모두 통과하기는 쉽지 않습니다.

따라서 예시에 주어진 것처럼 한 마리 씩 보내보면서 건널 수 있는지 없는지 체크하는 해법은 당연히 정답이 아닙니다. 답은 맞아도 시간이 너무 오래 걸립니다. 더욱 빠르게 하는 방법은 무엇이 있을까요? 우선 k만큼의 범위에 대해 생각해야 합니다.

k = 3, i = ?	stones[ i : i+k ]	몇 명 건너면 못 건너는가?
0	[2, 4, 5]	5
1	[4, 5, 3]	5
2	[5, 3, 2]	5
3	[3, 2, 1]	3
4	[2, 1, 4]	4
5	[1, 4, 2]	4
6	[4, 2, 5]	4
7	[2, 5, 1]	5
len(stones) - k 이후는 점프 가능하므로 통과	-	minimum = 3

k 단위만큼씩 잘라 sub list를 생성하면, maximum 값이 해당 sub list를 건널 수 있는 최댓값이 됩니다. 문제는 sublist에서 max를 구하는 방법을 나이브하게 구현하면 여전히 시간초과가 발생한다는 점입니다.

def solution(stones, k):
    count = -1
    for i in range(k, len(stones)+1):
        m = max(stones[i-k:i])
        if count == -1 or count > m:
            count = m
        
    return count

이를 극복하기 위한 힌트는, 정렬을 하면 정렬된 배열의 마지막 요소는 반드시 최댓값이라는 점과, sublist에 요소를 하나 제거하고 하나 추가하는데 sublist를 통째로 재구성할 필요 없다는 점입니다. 그리고 이전에 정렬된 배열에 요소를 순서에 맞게 추가할 수 있는 bisect.insort 함수에 대해 알아봤었죠. 이와 같은 논리가 적용되는 것입니다.

2021.05.20 - [알고리즘] - [HackerRank] Fraudulent Activity Notifications #이진탐색 #이분탐색 #바이너리서치 #bisect #sort

[HackerRank] Fraudulent Activity Notifications #이진탐색 #이분탐색 #바이너리서치 #bisect #sort

첫 시도에 sublist를 생성하면서 정렬하고, 이후에 요소를 추가할 때 insort 함수를 사용하면 따로 정렬이 필요하지 않습니다. 요소를 찾아서 제거할 때에도 이진탐색 bisect_left 함수를 사용하면 순회하며 찾는 것보다 훨씬 빠르게 동작합니다.

사실, 많은 문제를 풀어보고 비슷한 유형의 문제를 풀어봤기에 맞출 수 있었던 문제입니다. 다양한 사이트에서 많은 문제를 푸는 게 중요해보입니다.