프로그래머스 - 징검다리 건너기 파이썬

문제 

프로그래머스

정확성, 효율성 테스트가 모두 있는 문제

 

문제 이해

- stons: 디딤돌에 적힌 숫자가 순서대로 담긴 배열 

- k: 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수

- 디딤돌의 숫자는 한 번 밟을 때마다 1씩 감소 

- 디딤돌의 숫자가 0이되면 밟을 수 없고 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있음 

- 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 가장 가까운 디딤돌로만 건너뛸 수 있음 

- 건너뛰어야 하는 칸의 개수 > k라 못 건너는 상황, 총 위까지 3명이 건널 수 있음

 

제한사항 

- stones 배열의 크기는 1이상 20만 이하 

- stones 배열 각 원소들의 값은 1이상 2억 이하인 자연수 

 

접근법 

- 효율성 체크가 있다는 말은 완탐으로 풀면 시간초과가 난다는 뜻이라는 느낌적인 느낌 

 

- 처음 접근 방법(그럼에도 완탐으로 생각해봄)

-- 한 명씩 지나갈 때 돌의 값을 1씩 빼주고 

-- 0이 되는 돌을 체크 

-- 연속된 돌의 개수가 k가 될때를 체크 

-- 그리고 만나는 시간초과 

 

- 스톤의 최솟값, 최대값이 정해져있고, 적정값을 찾는 문제 == 이분탐색 

 

실패 코드 

def solution(stones, k):
    ans = 0
    left, right = 1, max(stones)  # 이진 탐색의 시작과 끝 범위 설정
    while left <= right:
        mid = (left + right) // 2  # 중간값 계산

        max_count = 0  # 최대 연속된 돌의 개수
        count = 0  # 현재 연속된 돌의 개수
        flag = False  # 0의 시작 여부를 판단하는 플래그
        for stone in stones:
            if stone - mid <= 0:  # 돌의 값이 중간값 이하인 경우
                if flag:
                    count += 1  # 연속된 돌의 개수 증가
                else:
                    max_count = max(max_count, count)  # 이전의 최대 연속된 돌의 개수와 비교하여 갱신
                    count = 1  # 현재 연속된 돌의 개수 초기화
                    flag = True  # 0의 시작으로 플래그 변경
            else:
                flag = False  # 연속이 끝났으므로 플래그 변경

        max_count = max(max_count, count)  # 마지막 연속된 돌의 개수와 비교하여 갱신

        if max_count >= k:  # 최대 연속된 돌의 개수가 k보다 크거나 같은 경우
            right = mid - 1  # 중간값을 감소시켜서 더 작은 범위에서 탐색
            ans = mid  # 현재 중간값을 정답으로 저장
        else:
            left = mid + 1  # 중간값을 증가시켜서 더 큰 범위에서 탐색

    return ans

 

성공코드 

def solution(stones, k):
    answer = 0
    start, end = 1, max(stones)
    
    while start <= end:
        middle = (start + end)//2  # 중간값 계산

        max_count = 0  # 최대 연속된 돌의 개수
        count = 0  # 현재 연속된 돌의 개수
        flag = False  # 0의 시작 여부를 판단하는 플래그
        
        # stones 리스트 순회
        for stone in stones:
            if stone - middle <= 0:  # 돌의 값이 중간값 이하인 경우
                if flag:
                    count += 1  # 연속된 돌의 개수 증가
                else:
                    max_count = max(max_count, count)  # 이전의 최대 연속된 돌의 개수와 비교하여 갱신
                    count = 1  # 현재 연속된 돌의 개수 초기화
                    flag = True  # 0의 시작으로 플래그 변경
            else:
                flag = False  # 연속이 끝났으므로 플래그 변경

        max_count = max(max_count, count)  # 마지막 연속된 돌의 개수와 비교하여 갱신

        if max_count >= k:  # 최대 연속된 돌의 개수가 k보다 크거나 같은 경우
            end = middle - 1  # 중간값을 감소시켜서 더 작은 범위에서 탐색
            answer = middle  # 현재 중간값을 정답으로 저장
        else:
            start = middle + 1  # 중간값을 증가시켜서 더 큰 범위에서 탐색

    return answer

개선한 점

- max(stones)보다 큰 값은 모두 0으로 처리되므로, 탐색 범위를 1부터 max(stones)까지로 설정하는 대신, 1부터 k까지로 범위를 좁히기

-돌의 개수를 기준으로 이진 탐색을 수행하는 대신, 최소 돌의 개수와 최대 돌의 개수를 기준으로 이진 탐색을 수행