[ 프로그래머스 ] 징검다리 건너기 (Python)

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

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : 이분탐색, 매개변수탐색
풀이 시간 : 24분 

문제 풀이 

- 징검다리는 일렬로 놓여있고, 디딤돌을 한 번 밟을 때마다 내구도가 1씩 깎인다.

- 내구도가 0이 되면 더이상 밟을 수 없으며, 이때는 그 다음 디딤돌로 여러칸을 건너 뛸 수 있다.

니니즈 친구들의 수는 무제한이라는 가정 하에 최대한 많이 건널 수 있는 니니즈 친구들의 수를 return하자.

 

문제의 입력 변수 범위를 살펴보면, $stones의 배열 크기 ≤ 200000$으로 주어졌다. 우리는 무한대의 숫자인 니니즈 친구들에 대해 완전탐색을 진행할 때, 최악의 경우 시간초과가 무조건 날 것임을 알 수 있다. 따라서 우리는 다른 알고리즘을 써야한다.

 

징검다리의 순서가 정해져있기 때문에, 정렬을 사용한 그리디 알고리즘도 힘들어 보인다. 그치만 문제에서 최대 몇 명까지 건널 수 있는지를 물어봤기 때문에 이분탐색으로 접근할 수 있을 것 같다.

 

먼저, 이분탐색에 사용할 범위 변수는 `건널 수 있는 사람 수`로 지정해주었다. 따라서, `left = 1`, `right = max(stones)`로 지정해주었다.

이후, 한 번 이분탐색을 진행할 때마다 stones 반복문 순회를 통해 깎인 내구도를 구해주었고, 만약 내구도가 0 보다 같거나 작아지는 경우엔 디딤돌이 무너졌다고 판단, 현재 망가진 연속적인 웅덩이 개수(`cnt`) + 1 을 진행해주었다.

 

마지막으로, 현재 망가진 웅덩이 개수와 뛰어넘을 수 있는 최대 값인 k를 비교해주어, 만약 현재 망가진 웅덩이 개수가 k보다 크거나 같은 경우에는, 현재 인원인 mid명으로는 딱 건너거나 건너지 못한다 판단하여 `answer = min(answer, mid)`로 지정해주었고, right = mid - 1로 줄여주었다. 만약 현재 망가진 웅덩이 개수보다 k가 크다면, 사람이 더 건널 수 있는 것으로 판단하여 left = mid + 1로 늘려주었다.

 

추가) 효율성 테스트를 따로 진행하는데, 이를 맞춰주기 위해 최대한 효율성을 높여서 작성해주었다.

1. 매개변수탐색을 위한 for문을 순회할 때, 인덱스 참조 대신 인덱스의 값 직접 참조를 사용하자.

# 이렇게 쓰지 말고
for i in range(len(stones)):
	...
    
# 이렇게 써야 시간초과가 나지 않는다.
for stone in stones:
    ...

2. 매개변수탐색 진행 중, 현재 연속적으로 망가진 웅덩이 개수가 k개와 같거나 넘어가는 시점이면 break를 통해 빠져나오자. → 이 경우에는 뒤에 돌멩이 값을 확인할 필요가 없게 된다.

 

코드

'''
1. 징검다리는 일렬로 놓여있고, 각 징검다리 디딤돌에는 숫자가 젹혀있으며, 밟을때마다 1씩 줄어든다
2. 숫자가 0이되면 더이상 밟을 수 없음. 이때는 그 다음 디딤돌로 여러칸 건너 뛸 수 있음
    - 무조건 다음 중 가까운 칸으로 건넌다.

stones <= 200000
풀이:
정렬하면 안된다.
이분탐색으로 풀이 가능할듯 ?
left = 1, right = max(stones)
건너면서 돌멩이 없어지는 경우에 cnt += 1 진행
'''

def solution(stones, k):
    answer = 0
    n = len(stones)
    
    left = 1
    right = max(stones)
    
    while left <= right:
        mid = (left + right) // 2    # 사람 수
        cnt = 0     # 현재 망가진 웅덩이 개수
        for i in stones:
            if i - mid <= 0:
                cnt += 1
            else:
                cnt = 0
            # 효율성 통과를 위한 break(임계값 k를 넘어가면 굳이 뒤에 부분 체크할 필요 없음)
            if cnt >= k:
                break
        if cnt >= k:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    
    return answer

배운 점 

사실 이렇게까지 빡씨게 효율성을 잡는 경우가 많이 있나 싶지만 ... 그래도 시간효율성을 높이기 위한 여러 가지치기, 인덱스 참조 방법 등을 배워갈 수 있었다.