[프로그래머스] 징검다리 건너기 (Python 풀이)

2019년 겨울 인턴 문제 징검다리 건너기 풀이 입니다.

프로그래머스에 올라와 있는 카카오 2019 인턴 4번 문제이다.

https://programmers.co.kr/learn/courses/30/lessons/64062
문제는 위 사이트를 참고를 하되 문제를 읽어보면서 중요하게 생각한 부분은 다음과 같다.

Problem Point
디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

문제에서 설명하는 부분대로 사람 한 명 한 명 지나갔을때 배열의 수를 차감하게 되면 시간 초과가 난 다는 것을 느꼇을 것이다. 처음에는 그래서 문제를 생각하다가 k 수의 윈도우 만큼 잘라서 max값을 구하고 그 중에서 min값을 구하는 방법을 생각하였다.

1차 생각

def solution(stones, k):
     answer = []
     for i in range(len(stones)-k+1):
         answer.append(max(stones[i:i+k]))
     return min(answer)

하지만 max값을 구하는 방법 자체도 O(n) 이기 때문에 이 풀이 자체는 O(n^2) 이다.
그래서 좀 더 생각하다가 한칸씩 건너가는 것이 아닌 각 윈도우에서 max값의 위치를 알아서 그 만큼 점프 하는 방식을 생각하였다. 예를 들어 start=0 , k=4 이고 해당 범위에서 최대값이 마지막 인덱스 이면 그 다음은 start=1 이 아닌 start=4으로 시작하는 것이다 .

2차 생각

def solution(stones, k):
    answer = []
    i = 0
    max_stone, index = 0, 0
    prev_Max, prev_index = 0, 0
    while i < len(stones)-k+1:
        for j in range(i, i+k):
            if max_stone <= stones[j]:
                max_stone = stones[j]
                index = j
        if prev_Max == max_stone and prev_index == index:
            max_stone = 0
            i += 1
        else:
            answer.append(max_stone)
            i = index
        prev_Max = max_stone
        max_stone = 0
        prev_index = index
    return min(answer)


stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
k = 3
print(solution(stones, k))

잘 풀었다고 생각하고 제출을 하였으나 효율성에서 하나를 통과하지 못하고 있었다. 코드 중간에 실수를 한 것인지 아니면 어떤 예외가 있을까를 생각하였는데 배열이 내림차순으로 정렬되어있다면 1차 생각때처럼 걸리는 시간이 O(n^2) 이 걸리는 케이스를 통과못한다고 생각하였다.

최종 풀이

def solution(stones, k):
    answer = 0
    l, r = 0, max(stones)
    
    while l <= r :
        cross = 0
        mid = (l+r)//2
        for stone in stones:
            if stone < mid:
                cross += 1
                if cross == k:
                    break
            else:
                cross = 0
        if k == cross:
            r = mid - 1
        else:
            answer = max(answer, mid)
            l = mid + 1
    return answer

해매다가 카카오 공식 풀이에서 이분탐색을 보고 풀이를 다시 작성하게 되었다. 카카오 문제를 풀다보면 이분탐색이 자주 나오는 것을 알 수 있는데 그것을 알아차리지 못하게 잘 내는 것 같다.