[프로그래머스] 2019 카카오 개발자 겨울 인턴십 징검다리 건너기

문제 설명

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

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

 

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그다음 디딤돌로 한 번에 여러 칸을 건너뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

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

---

제한사항

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

---

입/출력

입/출력

---

입/출력 예시

입출력 예 #1

첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.

첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.

---

문제 풀이

import copy

def solution(stones, k):
    left , right = 1 , max(stones)
    
    while left <= right :
        cnt = 0
        check = False
        mid = (left + right )//2
        tmp = copy.deepcopy(stones)
        
        for stone in range(len(tmp)):
            tmp[stone] -= mid 
        
        for i in range(len(tmp)):
            if tmp[i] <= 0:
                cnt += 1
            else:
                cnt = 0
                
            if cnt >= k:
                check = True
                break
                
        if check is True:
            right = mid - 1
        else:
            left = mid + 1
            
    return left

결과

---

문제 풀이

카카오 2019 겨울 인턴십 문제다. 처음 문제를 읽었을 때 뭐야 왜 이렇게 쉽지라고 생각했는데 제한사항에 200.000.000의 stone배열이 주어질 수 있다는 제한사항을 보고서는 역시 쉬운 게 하나 없군이라고 다시 생각하게 됐다.

선형 탐색으로 주어진 배열을 감소시키면서 문제를 풀어 나가면 정답은 나올 수 있으나 무조건 시간초과라는 결과를 받게 될 것이다.

 

다른 사람들의 문제 풀이를 보면 deque를 활용하여 해결하신 분도 계셨지만 테스트 케이스의 조건이 강화된 것인지 deque를 적용한 문제는 효율성 하나에서 정답을 받지 못했다.

 

주어진 제한 조건이 크기 때문에 선형 탐색을 하기 힘드니 이분 탐색을 적용하여 문제를 풀기로 했다. 오랜만에 이분 탐색으로 문제를 풀려고 하니 제대로 풀리지 않아서 힘들었다. 그래서 공책에 손으로 배열을 그리고 손 코딩하듯이 해보니 금방 이해가 됐다.

 

1. deepcopy를 적용해서 원본 배열에 대한 불변성을 유지하면서 문제를 풀었다.
2. tmp 배열은 stones와 같은 값을 가지며 각 인덱스마다 mid 만큼의 값을 감소시켜준다.
3. tmp 배열을 순회하면서 음수가 나오면 cnt에 1을 증가시켜준다.
4. 만약 순회하는 배열에서 음수가 아니라면 cnt를 다시 0으로 초기화시켜줘야 한다.
5. tmp 순회를 마친 후 k보다 크거나 같다면 True를 반환하고 right 값을 mid +1 한다.
6. 아니라면 left 값을 중간 값(mid)보다 1 증가시켜 다시 이분 탐색을 수행한다.
7. check가 True 라면 tmp배열이 모두 음수이고 cnt가 k보다 크거나 같으니  right = mid - 1을 하면 whil문이 종료된다.
8. left를 반환하면 정답처리를 받을 수 있다.

*제 이해가 잘못되었으면 언제든지 알려주시면 감사하겠습니다 !