[프로그래머스] 징검다리 건너기, Python3

[프로그래머스] 징검다리 건너기, Python3

문제 링크!

• 제한사항 및 유의사항
  • stones 배열의 크기는 1 ~ 200,000
  • stones 배열의 각 원소의 크기는 1 ~ 200,000,000
    • 위의 두가지 때문에 모든 경우의 수를 체크하기엔 효율성 채점에서 시간 초과 판정을 받을 것이다.
  • 친구들은 k를 넘은 칸 만큼 건널 수 없다.
    • k는 1 이상 stones길이 이하 자연수
• 풀이전략
  • 시간 초과 판정을 피하기 위해 이분 탐색으로 접근하자
    • 접근 시 탐색 기준값(mid)의 의미는 징검다리를 건널 수 있는 친구들의 수를 의미한다.
    • start = 1, end = max(stones)
      • start = 1인 이유 : 모든 stones[i] >= 1 임을 만족하므로
    • mid = (start + end) // 2
    • 매번 mid값 마다 해당 징검다리를 건널 수 있는지 체크한다.
      • stones를 순차적으로 돌면서 stones[i] - mid가 음수인지 체크한다.
        • 이 때, 연속된 음수일 경우를 체크하기 위해 카운트를 세어준다.
        • 이 카운트가 k와 같은 경우 False를 리턴해준다.

코드를 먼저 본 다음 그림으로 설명드리겠습니닷

def possible(stones, k, mid):
    count = 0
    for stone in stones:
        # 음수인 경우는 건너지 못한 경우이므로 이 구간마다 count += 1 해주기
        if stone - mid < 0:
            count += 1
            # 연속된 음수가 k개인 경우 바로 False를 리턴한다.
            if count >= k:
                return False
        # 연속되지 않은 경우이므로 count = 0으로 초기화
        else:
            count = 0
    return True


def solution(stones, k):
    answer = 0
    # 초기값 설정
    start, end = 1, max(stones)
    while start <= end:
        mid = (start + end) // 2

        # 해당 인원이 징검다리를 건널 수 있는지 체크
        if possible(stones, k, mid):
            answer = max(answer, mid)
            start = mid + 1
        else:
            end = mid - 1
    return answer

그 다음 그림으로 예제를 만들어 보았습니다.

• stones = [2, 3, 4, 3, 1, 1, 2]
• k = 2

1. 우선 맨 한명이 건넌 경우, 최솟값이 0 이므로 간격에 상관없이 1명은 건널 수 있습니다.
2. 2번째 친구가 건너고 나서는 연속된 음수가 2개 있습니다. 연속된 음수의 갯수가 k와 같거나 크면 건널 수 없습니다!
3. 해당 mid(건너려고 하는 친구들의 수)를 위의 방식처럼 stones 배열에서 mid를 빼고 연속된 음수의 갯수를 파악하면 답을 얻을 수 있고, 이분 탐색으로 접근했기 때문에 시간 초과판정도 받지 않습니다!