[프로그래머스][이분탐색] 징검다리 건너기

징검다리 건너기

프로그래머스

 

 

N = 200,000, M = 200,000,000

첫 번째 시도 (슬라이딩 윈도우 방식) - Fail 

• 슬라이딩 윈도우로 접근
  • 사람이 건널 때, 연속으로 k개의 디딤돌이 모두 무너져선 안 됨
    
    • 따라서 해당 범위 내의 max값이 건널 수 있는 최대 인원이라 생각
  • 전체 윈도우에서의 max값 중 최솟값 = 건널 수 있는 최대 인원 수
• 하지만 시간 복잡도는 다음과 같음

슬라이딩 윈도우 범위: N
max()로 각 구간 max 값 탐색: O(N)

→ 전체 시간 복잡도: O(N × N) = O(N²)  시간 초과

• 투 포인터 등으로 시간 단축을 시도했으나, 적절한 최적화 방식을 찾지 못해 실패

def solution(stones, k):
    answer = float('inf')
    n=len(stones)
    max_value=
    for i in range(0,n-k+1):
        answer=min(answer,max(stones[i:i+k]))
    return answer

---

보완된 슬라이딩 윈도우 방식 (deque 활용) - Success

• 슬라이딩 윈도우 내 최댓값을 빠르게 구하기 위해 deque를 사용
• monotonic queue 방식으로 구성하면, 각 값이 한 번만 deque에 들어갔다 나가므로 전체 시간 복잡도는 O(N)
• 윈도우 벗어나는 길이는 제거해주고
• 새로운 값을 넣었을 때, 뒤에서부터 현재값보다 작거나 같은 값은 모두 제거
  • 가장 큰 값만 남김 = 결국 그 윈도우 범위내의 최댓값을 찾는 것
• 그 최댓값들 중 최솟값 탐색 

from collections import deque

def solution(stones, k):
    answer = float('inf')
    dq = deque()
    
    for i in range(len(stones)):
        # 윈도우 벗어난 인덱스 제거
        while dq and dq[0] <= i - k:
            dq.popleft()
        # (뒤에서부터) 현재 값보다 작거나 같은 값은 모두 제거
        while dq and stones[dq[-1]] <= stones[i]:
            dq.pop()
        dq.append(i)
        # 윈도우 시작 시점부터 결과 계산
        if i >= k - 1:
            answer = min(answer, stones[dq[0]])
    
    return answer

---

정답 풀이 (이분 탐색)

• 사실 이 문제의 본질은 결정 문제로 바꾸는 것
  • "사람 수 x명을 보냈을 때, 건널 수 있는가?"
• 이 조건을 만족하는 최대값을 찾아야 하므로, 이분 탐색을 적용
• 이분 탐색 범위: left = 1, right = M
• 중간값 mid를 현재 건너는 인원 수라고 가정하고 stones를 순회하며 판단
  • 각 디딤돌에서 stone - mid < 0이면 밟을 수 없음  → cnt로 횟수 체크
  • 연속으로 밟을 수 없는 디딤돌이 k개 이상 나오면 해당 인원은 실패
    • 인원이 너무 많았으므로 줄임: right = mid - 1
  • 중간에 실패하지 않고 끝까지 건널 수 있으면 해당 인원까지는 가능
    • 더 많은 인원이 가능한지 확인: left = mid + 1
• 이분 탐색으로 가능한 최대 인원을 탐색함

 

이분 탐색 범위: log₂(M) = log₂(200,000,000) ≈ 28회
각 판별: O(N) = 최대 200,000
→ 총 시간 복잡도: O(N × log M)

 

def solution(stones, k):
    left = 1
    right = max(stones)
    answer = 0

    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        max_cnt = 0

        for stone in stones:
            if stone < mid:
                cnt += 1
                if cnt >= k:
                    break
            else:
                cnt = 0

        if cnt < k:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer