문제 설명

문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

입출력 조건

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

---

전체 코드

def solution(stones, k):
    answer = 0
    
    left=1
    right= 200000000 
    
    while left<=right:
        mid=(left+right)//2
        
        count=0
        
        cant_go=False
        
        for i in range(len(stones)):
            if stones[i]-mid<0:
                count+=1
                if count>=k:
                    cant_go=True
                    break
            else:
                count=0
        
        if cant_go==True:
            right=mid-1
        else:
            left=mid+1
                      
    
    answer=right
    
    return answer

---

해설

단순히 2중 반복문으로 풀면 시간초과가 나는 문제이다. 즉 O(N^2)보다 빠른 시간으로 풀어야 한다.

건너갈 수 있는 인원은 1명 ~ 200000000명 사이의 수에 해당하므로 이분 탐색을 활용하면 O(NlogN)의 시간으로 풀 수 있다.

left=1, right=200000000으로 시작해서 둘의 중간 값 mid를 구한다.

stones를 순회하면서 stones[i]가 mid보다 작다면, 인원이 mid명일 때 해당 구역은 뛰어 넘어가야 하는 것이라 볼 수 있다. 만약, 연달아 뛰어 넘는 것이 k를 넘으면 mid명일 때는 징검다리를 건널 수 없는 것이다.

징검 다리를 mid명일 때 건널 수 없다면, 최대 범위에 해당하는 right을 mid-1로 조정한다.

그렇지 않다면, 최소 범위에 해당하는 left를 mid+1로 조정한다.

이러한 반복은 left≤right이 아닐 때, 즉 처음으로 left>right일 때 종료된다.

left>right이 되는 상황에서의 가장 마지막 right 값이 정답이 된다.

---

1차 풀이

일부 시간 초과

def solution(stones, k):
    
    answer=0
    
    # 사람이 건널 수 있는 범위는 stones 배열 원소의 값 범위와 같다.
    start=1
    end=200000000
    
    # 징검다리를 건널 수 있는 사람의 수의 정답 '범위'를 줄이자. O(logN)
    while start<=end:
        
        mid=(start+end)//2
        
        # mid 명이 지나갔을 때 남은 돌 숫자들 (0 이하이면 더 이상 못 밟는다.)
        stones_after_mid=[stone-mid+1 for stone in stones]
        
        not_passible_count=0
        
        exceed_number_of_people=False
        
        for stone_value in stones_after_mid:
            if stone_value<=0:
                not_passible_count+=1
            else:
                not_passible_count=0
            
            if not_passible_count>=k:
                exceed_number_of_people=True
                break
        
        if exceed_number_of_people:
            end=mid-1
        else:
            answer=max(answer,mid)
            start=mid+1
            
    return answer

일부 효율성 시간 초과의 원인은 stones_after_mid=[stone-mid+1 for stone in stones] 코드 때문이다. 새로운 배열 생성이기 때문에 O(20만)을 추가 소요하게 된다.

테케 8 효율성 실패

def solution(stones, k):
    
    answer=0
    
    # 사람이 건널 수 있는 범위는 stones 배열 원소의 값 범위와 같다.
    start=1
    end=200000000
    
    # 징검다리를 건널 수 있는 사람의 수의 정답 '범위'를 줄이자. O(logN)
    while start<=end:
        
        mid=(start+end)//2
        
        not_passible_count=0
        
        exceed_number_of_people=False
        
        for stone_value in stones:
            if stone_value-mid+1<=0:
                not_passible_count+=1
            else:
                not_passible_count=0
            
            if not_passible_count>=k:
                exceed_number_of_people=True
                break
        
        if exceed_number_of_people:
            end=mid-1
        else:
            answer=max(answer,mid)
            start=mid+1
            
    return answer

원인은 answer=max(answer,mid)때문이었다.

정답 코드

def solution(stones, k):
    
    # 사람이 건널 수 있는 범위는 stones 배열 원소의 값 범위와 같다.
    start=1
    end=200000000
    
    # 징검다리를 건널 수 있는 사람의 수의 정답 '범위'를 줄이자. O(logN)
    while start<=end:
        
        mid=(start+end)//2
        
        not_passible_count=0
        
        exceed_number_of_people=False
        
        for stone_value in stones:
            if stone_value-mid+1<=0:
                not_passible_count+=1
            else:
                not_passible_count=0
            
            if not_passible_count>=k:
                exceed_number_of_people=True
                break
        
        if exceed_number_of_people:
            end=mid-1
        else:
            start=mid+1
            
    return end

---

1차 풀이 느낀 점

1. 예전에 이분 탐색으로 풀었다는 게 기억나는 상태로 풀었다.
2. 그런데 1.을 몰랐다면, 과연 이분 탐색을 떠올릴 수 있었는지 의문이다.
3. 예전에 푼 해설에서 left>right이 되는 상황에서의 가장 마지막 right 값이 정답이 된다. 라는 것을 분석할 필요가 있다.

왜 이분탐색인지 나름대로 분석해봄

가장 간단한 해법인 브루트 포스를 적용한다고 해보자. 돌 배열 길이를 len, 돌의 숫자의 값의 범위를 value_range이라 하자.

최악의 경우 돌의 숫자 값이 200000000으로만 되어 있는 배열의 길이가 200000이라고 하면, 시간 복잡도가 O(200000000 x 200000)으로 어마어마한 숫자가 나온다.

사람의 수를 x라 할 때, x가 전부 지나갈 수 있는 지 판별하려면 어쨋든 돌 배열 길이만큼은 탐색을 해봐야 한다. 즉, O(len)은 계산에서 상수라고 볼 수 있다. 더 줄일 수가 없는 것이다.

돌의 숫자 값의 범위 O(value_range)가 시간 복잡도를 줄일 수 있는 유일한 변수인데, 여기서 value_range는 이름 그대로 값의 범위이기 때문에 최대, 최소, 범위 키워드와 많이 관련이 있는 이분 탐색을 적용할 수 있지 않았나 싶다.

구체적인 것은 나중에 또 파봐야 할 듯...