[프로그래머스/Lv.3] - 징검다리 건너기

ZenTechie·2023년 7월 4일

programmers ps

PS

목록 보기

27/53

징검다리 건너기 문제 링크

아이디어

문제의 제한사항의 일부를 보면 다음과 같다.

징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
stones 배열의 크기는 1 이상 200,000 이하입니다.
stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.

위의 조건 때문에 $O(N^2)$ 은 당연히 불가능하다.

우리가 원하는 것은 건널 수 있는 최대 사람의 수이다. 여기서 이진탐색을 떠올렸다.

기본 아이디어는, 사람 수를 기준(mid)으로 설정하고 stones 배열의 각 원소에서 mid만큼 뺀 후 연속되는 0의 최대 길이를 찾는 방식이다.

코드

실패

def solution(stones, k):
    def helper(stones):
        n = len(stones)
        _max = 0
        start = -1
        for i in range(n):
            if stones[i] == 0:
                if start == -1:
                    start = i
            else:
                if start != -1:
                    _max = max(_max, i - start + 1)
                    start = -1
                continue
        return _max
    
    answer = 0
    l, r = 1, max(stones)
    while l <= r:
        mid = l + (r - l) // 2
        new_stones = [stone - mid if stone >= mid else 0 for stone in stones]
        _max = helper(new_stones)
        if _max < k:
            l = mid + 1
        elif _max >= k:
            answer = _max
            r = mid - 1
        
    return answer

풀이

알고리즘은 크게 2가지이다.

연속된 0의 길이 찾기
이진탐색 수행

연속된 0의 길이 찾기

처음에 어떻게 0의 길이를 찾을 것인가 고민을 하다가, 포인터(start)를 하나 사용해서 현재 탐색중인 원소의 값이 0이면 해당 원소의 위치로 포인터를 갱신한다.

그리고 만약, 0이 아닌 원소를 마주친다면 현재 원소의 위치에서 포인터까지의 길이를 구해 저장해 _max(연속된 0의 길이의 최댓값)과 비교하여 저장한다.

문제의 예시 입력은 성공하지만, 다른 테스트 케이스는 모두 틀리는 것을보아 이 알고리즘이 문제인 것 같다.

성공

def solution(stones, k):
    # 연속적인 0의 길이(개수) 찾는 함수
    def find_consecutive_zero_length(stones, mid):
        zero_cnt = 0 # 0의 길이
        for stone in stones:
            if stone - mid <= 0:
                zero_cnt += 1
            else:
                zero_cnt = 0
                
            # 주어진 k보다 크거나 같다면
            # 즉, 건널 수 있는 칸의 수보다 같거나 많게 건너 뛰었음을 의미.
            if zero_cnt >= k: 
                break
        
        return zero_cnt
    
    # 이진 탐색 포인터
    # 기준 : 다리를 건널 수 있는 최대 사람 수
    l, r = 1, max(stones)
    answer = 0
    
    while l <= r:
        mid = (l + r) // 2
        zero_cnt = find_consecutive_zero_length(stones, mid) # 연속적인 0의 길이
        
        if zero_cnt >= k: # 너무 많이 or 딱 맞게 칸을 건너 뜀
            answer = mid
            r = mid - 1 # 왼쪽 부분 탐색
        else: # 너무 적게 칸을 건너 뜀
            l = mid + 1 # 오른쪽 부분 탐색
        
    return answer