[Programmers] 징검다리 건너기

문제

요약

징검다리를 건너는 데 돌마다 건널 수 있는 횟수가 정해져 있음

Ex) 횟수가 3인 돌을 한사람이 건너면 2가 됨.

건너 뛸 수 있는 돌의 개수는 k 개

최대 몇 명이 다리를 건널 수 있는가?

 

원본

https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

---

풀이

챕터별로 나누어 풀고 있기 때문에 이진 탐색을 써야 하는 건 알겠는데

어느 부분을 이진 탐색을 하라는 건가,,, 저번에 이진 탐색 풀때랑 같은 문제,,,

 

다 풀고 난 지금에야 약간의 방식을 알게 된 것 같다.

이진 탐색 문제에서 어느 부분을 이진 탐색 해야할 지 모르겠다면 일단 주어지는 배열을 본다.

1. 배열로 주어진 것

2. 배열로 주어진 것이 정렬 할 수 없거나 중복된 수가 많다면, 중복 제거한 배열

3. 배열의 값을 바로 하는 것이 아니라 배열의 인덱스

 

풀이 방식은 2+3번이다.

1. 돌에 있는 횟수를 중복 제거하여 정렬 해준다.

2. 정렬된 돌을 이진 탐색을 통해 적절한 값을 찾아가는 과정

    2-1. 정렬된 돌의 최대와 최소 인덱스를 이진탐색해서 값을 정한다.

    2-2. 원래 배열(stones)의 처음부터 끝까지 값을 비교한다.

    2-3. stones의 값이 크거나 같으면, 현재 밟고 있는 위치를 갱신해 준다.

    2-4. stones의 값이 작으면, 건너 뛰는데 k번까지만 건너 뛸 수 있다.

    2-5. k회를 넘기면 최대 값을 현재 값보다 작게 설정하여 다시 이진 탐색한다.

    2-6. stones를 순회했다면, answer를 현재 값으로 갱신하고, 최소값을 현재 값보다 크게 설정하여 다시 이진 탐색한다.

3. 위 과정을 lw가 up보다 커질때까지 반복한다.

 

여기서 주의할 점은 다리를 건너는 것은 돌의 마지막에서 땅을 밟는 데 까지라는 것이다.

즉, stones에서 마지막 인덱스 + 1까지 건널 수 있어야 한다. 

이 부분 때문에 효율성이랑 정확도에서 1문제씩 틀렸다.

해당되는 반례는 아래와 같다.

 

[input]
[2, 4, 5, 3, 2, 1, 4, 2, 2, 1] 3

[output]
2

def solution(stones, k):
    answer = 0
    temp = sorted(list(set(stones)))
    l = len(stones)
    lw = 0
    up = len(temp) - 1 
    
    while lw <= up:
        mid = (lw+up) // 2
        now = -1
        
        for i in range(l+1):
            if i - now <= k:
                if i!=l and stones[i] >= temp[mid]:
                    now = i
            else:
                up = mid - 1
                break
        else:
            answer = temp[mid]
            lw = mid + 1
    
    return answer