파이썬(Python) 알고리즘 문제풀이 징검다리 건너기 [프로그래머스 / 이분탐색]

출처) 프로그래머스 Facebook

문제 설명

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

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

 

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

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

 

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

 

 

제한사항

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

 

 

입출력 예시

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

 

 

 

풀이 코드

이진 탐색을 빼놓고 생각해보자면 반복문을 순회하며 건널 수 없는 구간이 있을 때 까지 니니즈 친구들 수를 하나 씩 더하는 방법이 있긴한데, 제한사항에 니니즈 친구들의 수는 무제한, 1 <= len(stones) <= 20만까지, 1 <= stones[i] <= 2억까지 주어지기 때문에 최악의 경우 O(2억 * 20만) 만큼 순회해야하기 때문에 단순히 생각해봐도 위 방법으로는 시간복잡도 면에서 절대 통과할 수 없는 알고리즘이 될 것이다.

 

제한 사항에서 느낌이 오듯 이 문제 또한 대놓고 이진 탐색으로 풀이하는 문제인데, 역시 어떤 것을 임의의 기준 값으로 삼아야하는지 고민해보자. 구해야 하는 값은 징검다리를 건널 수 있는 최대한의 니니즈 친구들 명수를 구해야하니까 임의의 기준 값을 니니즈 친구들 수로 가정해보자. start 는 최악의 경우, end 는 최고의 경우라고 했을 때 최악의 경우 아무도 징검다리를 건널 수 없으니 0명으로 초기화하면 될 것 같고, 최고의 경우 모든 니니즈 친구들이 건널 수 있는 경우인 max(stones) 로 초기화하면 될 것 같다. 최고의 경우가 애매하면 2억으로 잡아도 무방하다. 마지막으로 최대 값 갱신을 위해 변수 하나를 -1e15 로 초기 값으로 초기화해두자.

 

여기까지 코드는 아래와 같다. 

def solution(stones, k):
    answer = -1e15
    start, end = 0, max(stones)

	while start <= end:
    	mid = (start + end) // 2

 

 

이제 mid 명이 징검다리를 건널 수 있을까 ? 를 판단하면 된다.

즉, mid 명 만큼 건너지 못하는 상황에서 mid 명을 줄이고, 충분히 건널 수 있는 상황에서는 mid 명을 늘리면 된다. 건너지 못하는 상황은 어떻게 판단할 수 있을까 ? 입출력 예제 4번째 그림을 봤을 때,  연속적으로 디딤돌 숫자가 0인 디딤돌 개수가 발견됐고, 이게 한 번에 돌을 건너뛸 수 있는 개수인 k 보다 같거나 클 때 건너뛸 수 없음을 알 수 있다. 즉, 건너뛰어야 하는 돌이 연속적으로 몇 개가 발견되는가 구하는 것이 문제 풀이의 핵심이라고 할 수 있다.

 

현재 디딤돌 숫자보다 mid 명이 더 크다면 해당 디딤돌은 건너뛰어야 하는 돌이므로 건너뛰어야 하는 돌 개수를 하나 늘리고 현재 디딤돌 숫자보다 mid 명이 작거나 같다면 연속적으로 건너뛰어야 하는 돌이 발견된 것이 아니니까 건너뛰어야 하는 돌 개수를 0으로 다시 초기화시켜준다. 디딤돌을 끝까지 확인하는 경우가 아닐지라도 건너뛰어야하는 디딤돌 개수가 k 값보다 크거나 같은 경우 현재 mid 명 만큼 징검다리를 건널 수 없다는 것이기 때문에 break 로 반복문을 탈출하도록 한다.

 

예를 들어 stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1], mid = 4 라고 가정했을 때를 살펴보자.

 

1. 현재 디딤돌 2는 임의의 사람 수 4보다 작기 때문에 건너뛰는 돌 개수 증가 (1)

2. 현재 디딤돌 4는 임의의 사람 수 4와 같기 때문에 건너뛰는 돌 개수 초기화 (0)

3. 현재 디딤돌 5는 임의의 사람 수 4보다 크기 때문에 건너뛰는 돌 개수 초기화 (0) -> 돌 개수 증가 아니니 그냥 초기화로 퉁친 거

4. 현재 디딤돌 3은 임의의 사람 수 4보다 작기 때문에 건너뛰는 돌 개수 증가 (1)

5. 현재 디딤돌 2은 임의의 사람 수 4보다 작기 때문에 건너뛰는 돌 개수 증가 (2)

6. 현재 디딤돌 1은 임의의 사람 수 4보다 작기 때문에 건너뛰는 돌 개수 증가 (3)

7. 건너뛰어야 하는 돌 개수가 이미 k 보다 크거나 같아졌기 때문에 반복문 break

 

여기까지 코드는 아래와 같다.

def solution(stones, k):
    answer = -1e15
    start, end = 0, max(stones)

	skip_stone_count = 0
	while start <= end:
    	mid = (start + end) // 2
        
        for stone in stones:
        	if stone < mid:
            	skip_stone_count += 1
                
                if skip_stone_count >= k:
                	break
                    
            elif stone >= mid:
            	skip_stone = 0

 

 

그 다음, 건너뛰어야 하는 돌 개수로 mid 명을 조절하면 문제를 해결할 수 있다. 이진 탐색 문제라도 무조건 주어진 리스트를 정렬하고 푸는건 아니다. 이 문제처럼 stones 리스트를 절대 건드리면 안되는 경우도 있고 이 풀이 방법에서 기준을 잡은 임의의 mid 명은 0명 ~ max(stones) 명 사이에서 mid 값이 조정되기 때문에 따로 정렬이 필요 없는 경우라 리스트를 정렬하지 않았다. 마지막으로 모든 풀이 코드는 아래와 같다.

def solution(stones, k):
    answer = -1e15
    start, end = 0, max(stones)

	skip_stone_count = 0
	while start <= end:
    	mid = (start + end) // 2
        
        for stone in stones:
        	if stone < mid:
            	skip_stone_count += 1
                
                if skip_stone_count >= k:
                	break
                    
            elif stone >= mid:
            	skip_stone_count = 0
                
        if skip_stone_count >= k:
			end = mid - 1
            
        # 니니즈 친구들 mid 명이 건너갈 수 있는 경우
        # 여기서 최대 값을 구해준다.
        elif skip_stone_count < k:
            start = mid + 1
            answer = max(answer, mid)
    
    return answer