[Python/이분탐색] 징검다리 건너기

prefer_all 2022. 12. 12. 09:50

문제 설명

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

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

징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 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

예시 설명

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

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

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

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

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

풀이

stones의 모든 원소를 1씩 빼가면서 '연달아 0인 원소의 개수가 언제 k가 되는 가'를 찾는 문제였다.

연달아 음수가 나오는 최대 수를 반환하는 함수 check을 사용한 첫 풀이는 시간 초과가 났다.

''' # *** 오답(정확성 테스트 통과, 효율성 테스트 통과 못함)***
디딤돌을 밟을 때마다 1씩 줄어들고 숫자가 0이 되면 밟을 수 없음
그 다음 디딤돌로 여러 칸 건너뛰기 가능

stones: 디딤돌에 적힌 숫자
k: 한 번에 건너뛸 수 있는 최대 칸 수
최대 몇 명까지 징검다리를 건널 수 있는 가
'''
def check(stones): # 연달아 0인 원소의 개수 반환
    cnt, tmp = 0, 0 # 연속된 0의 개수의 최대값
    for i in range(len(stones)):
        if stones[i] <= 0:
            tmp += 1
            cnt = max(cnt, tmp)
            continue
        else:
            tmp = 0
    return cnt

def solution(stones, k):
    answer = 0
    while True:
        num = check(stones)
        if num >= k:
            return answer
            break
        else:
            stones = [x-1 for x in stones]
            answer += 1

이진탐색을 사용해 건널 수 있는 최대 인원의 수를 찾는 접근법이 필요한 문제였다.

건널 때 stones의 상황은 고려하지 않는다.

1. 초기 상태: 건널 수 있는 인원의 수는 stones의 최소, 최댓값 사이의 값이다.

2. n명이 건널 수 있는 지를 확인하기 위해서는 다음과 같이 확인하면 된다.

stones의 원소에 n을 뺀 값이 음수인 경우가 k개보다 많은 경우 건널 수 없다.=> right를 mid-1로 범위를 조정해준다

stones의 원소에 n을 뺀 값이 음수인 경우가 k개보다 적은 경우 더 많이 건널 수 있다. => left를 mid+1로 범위 조정

# *** 실패 (정확성 테스트는 통과하나, max를 사용해서 일부 시간 초과) ***
def solution(stones, k):
    answer = 0
    left, right = min(stones), max(stones) 
    
    while left <= right:
        mid = (left + right)//2
        cnt, tmp = 0, 0
        
        for s in stones: # mid명이 건널 수 있는 지를 확인
            if s-mid <= 0: # 0이 연속적으로 나오는 경우
                tmp += 1
                cnt = max(cnt, tmp)
            else:
                tmp = 0 # 0이 연속적으로 안 나오면 초기화

        if cnt < k: # 더 많이 건널 수 있음
            left = mid + 1
        else: # 덜 건너야 함
            answer = mid
            right = mid -1
            
    return answer

def solution(stones, k):
    answer = 0
    left, right = min(stones), max(stones) 
    
    while left <= right:
        cnt = 0
        mid = (left + right)//2
        for s in stones: # mid명이 건널 수 있는 지를 확인
            if s-mid <= 0: # 0이 연속적으로 나오는 경우
                cnt += 1
            else:
                cnt = 0 # 0이 연속적으로 안 나오면 초기화
            if cnt >= k: # 더 이상 건널 수 없는 경우 ⭐⭐⭐
                break 
        if cnt < k: # 더 많이 건널 수 있음
            #answer = mid
            left = mid + 1
        else: # 덜 건너야 함
            answer = mid
            right = mid -1
            
    return answer

📝

리스트에서 같은 값이 몇 개나 연속됐는 지 확인

arr = [1,2,3,0,0,0,4,0,5]
cnt, tmp = 0, 0 # 연속된 0의 개수의 최대값

for i in range(len(arr)):
    if arr[i] == 0:
        tmp += 1
        cnt = max(cnt, tmp)
        continue
    else:
        tmp = 0

print(cnt)

참고