[Programmers][Python] 징검다리 건너기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

 

처음 작성한 코드

슬라이싱을 이용하여 리스트를 한 번만 확인한다.

개인적으로 생각했을때 문제의 출제의도는 '20만 번의 배열 크기', 자연수의 범위라는 조건과 탐색이라는 조건을 생각했을 때 바이너리 서치를 이용하여 시간복잡도를 O(nlogn)까지 줄이라는 의미이다. 하지만 DP? 를 이용해 조금 더 줄여보자.

• k범위의 디딤돌이 모두 소모가 되었을 때 징검다리를 건널 수 없다.
  • 이 의미는 k범위 내의 디딤돌 중 제일 큰 숫자 만큼 징검다리를 이용할 수 있다는 이야기이다.
  • 모든 k범위에서의 가장 큰 값들 중 가장 작은 값이 총 친구들이 건널 수 있는 인원이 된다.
• 이제 윈도우를 k만큼 설정하고 for range를 이용해 한 단계씩 확인해 본다.
  • 우선 값을 빼고 넣기 쉽게 deque로 윈도우를 구현해 주자
  • 인덱스가 증가하는 방향으로 확인하므로, 자기 인덱스보다 낮은 인덱스의 값이 자기 값보다 작다면 앞으로도 윈도우 안에서 사용될 일은 없다.
  • 따라서 while 문을 이용해 윈도우안의 값이 다음 인덱스로 들어온 값보다 작은 경우 제거한다.
  • 이렇게 되면 deque로 이루어진 윈도우는 압축이 되고 항상 0번 인덱스는 윈도우 내 최댓값의 인덱스가 된다.
  • 쉽게 알 수 있는 최댓값을 다른 리스트에 저장해 준다.
  • 윈도우를 이동시켜 만료된 인덱스는 모두 제거해 주는 걸 잊지 않는다.
• 각 k범위의에서 가장 큰 값들을 모았으므로, min 함수를 이용해 최솟값을 구해준다.

from collections import deque

def solution(stones, k):
    deq = deque()
    max_values = []

    # 초기 윈도우 설정
    for i in range(k):
        # 자기보다 낮은 인덱스의 값이 낮으면 의미가 없다
        # 이렇게 가장 왼쪽에는 윈도우내에서 가장 큰 값의 인덱스가 유지 된다.
        while deq and stones[i] >= stones[deq[-1]]:
            deq.pop()
        deq.append(i)

    # 첫 윈도우의 최대값 추가
    max_values.append(stones[deq[0]])

    # 슬라이딩 윈도우 처리
    for i in range(k, len(stones)):
        # 만료된 인덱스 제거
        while deq and deq[0] <= i - k:
            deq.popleft()
        while deq and stones[i] >= stones[deq[-1]]:
            deq.pop()
        deq.append(i)
        max_values.append(stones[deq[0]])

    return min(max_values)
    
# 테스트
print(solution([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3))  # 3

이렇게 작성한 알고리즘은 O(n) (윈도우가 데이터를 훑기) + O(n) (deque에 들어가고 확인하는 경우도 n에 가까움) + O(logn) (마지막에 최솟값 찾기) -> O(n)의 복잡도에 가깝다. 물론 max_values에 매번 데이터를 저장해야 하기 때문에 메모리를 조금 더 쓴다는 단점은 있다.

 

다른 코드

바이너리 서치를 이용해 보자.

아마 문제가 요구하는 바이자 넓게 사용될 수 있는 알고리즘이다.

• 건널 수 있는 친구는 무한대이지만, 디딤돌은 제한이 있으므로 max 함수를 이용해 돌의 최댓값을 구한다.
  • 바이너리 서치 알고리즘을 이용해 매번 중간값의 친구가 건널 수 있는지 확인해준다.
  • 중간값만큼 친구들이 건널 수 있는지는 stones 리스트를 확인하여 연속으로 디딤돌의 숫자가 친구 인원보다 적으면 건널 수 없는 조건을 이용해 확인한다.

# mid 만큼 건널 수 있는 돌의 개수가 연속으로 k가 나오는지 확인
def can_cross(stones, k, mid):
    cnt = 0
    for stone in stones:
        if stone - mid < 0:
            cnt += 1
            if cnt == k:
                return False
        else:
            cnt = 0
            
    return True

def solution(stones, k):
    left, right = 1, max(stones)
    answer = 0
    
    while left <= right:
        mid = (left + right) // 2
        if can_cross(stones, k, mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    
    return answer

이렇게 작성된 알고리즘은 최악의 경우 O(nlogn)에 가깝다. 하지만 문제의 조건을 보았을 때 구현하기 쉽고 문제없이 통과한다.

 

사담

두 코드의 효율성 테스트이다.

DP(왼쪽), 바이너리 서치(오른쪽)