[프로그래머스] 징검다리 건너기

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

🔎[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

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

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

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

---

출처: 프로그래머스

 

[입출력 예]

출처: 프로그래머스

사람의 직관으로는 어렵지 않은 문제나, 컴퓨터를 통해 구현하고자 하니 까다로운 문제였다.

 

stones 배열 제한이 200,000, 각 원소 제한이 200,000,000이고 효율성 테스트까지 통과해야하므로 단순히 모든 돌을 1씩 감소시키면서 문제를 풀면 시간 제한을 통과할 수 없다.

 

그래서 처음 생각한 방법은, stone배열을 정렬해서 k번째 원소만큼 빼고 시작하는 것이었다.

이 방법은 결국은 1씩 감소 시키는 걸 조금 더 가속화 시켜줄 뿐, 시간 복잡도 개선에 별 기여를 하지 못했다.

 

방법은 '이분 탐색'에 있었다.

처음에 이분 탐색이라는 힌트를 봤을 때 돌의 순서가 정해져있어서 정렬하지 못하는데 이분 탐색이 가능한가? 의문을 가졌었다. (이분 탐색은 원래 정렬된 배열에 시행하는 탐색 알고리즘이다.)

 

<정답 코드>

def solution(stones, k):
    left, right = 0, max(stones)
    
    while left <= right:
        mid = (left+right)//2
        flag = 0
        for s in stones:
            if s-mid < 0:
                flag += 1
                if k <= flag:
                    break
            else:
                flag = 0
            
        if k <= flag:
            right = mid-1
        else:
            left = mid+1

    return left-1

이 문제에서 이분 탐색의 개념은 배열에 적용하는게 아니라 윈도우(범위)에 적용되는 것이었다.

 

접근은 아래와 같다.

1. stones원소의 최대 값을 구한다.
2. 돌에서 뺄 원소 값을 left와 right의 중간값으로 하여 전체 돌을 순회한다.
3. flag를 통해서 0보다 작은 값이 되는 돌들을 카운트 한다.
   1. 0보다 크면 flag를 0으로 초기화한다.
4.  flag가 k가 되면 for문을 탈출한다.
5. 이후 윈도우의 크기를 절반으로 줄여 다시 진행한다.

이 방법을 시도하면서 들었던 의구점은 left나 right의 값이 stone의 원소와 일치하지 않는다면 정렬을 통해 진행했던 내 방법보다 나은게 뭐가 있지? 라는 생각이었다.

 

그래서 다시 값의 개수 자체를 줄이고자 set을 활용해서 진행해보고자 했으나, set으로 전환하고 list로 바꾸고 sort까지 하는 과정에서 시간 복잡도를 너무 잡아먹어서 포기하기로 했다..

 

*해당 문제를 deque와 sliding window maximum을 통해 해결할 수 있다는 글을 보았다. 원리 자체가 아예 이해 안가지는 않았지만, 여러번 작성해봐도 실제로 작동하는 코드를 짤 수 없었다. 이후에 다시 한번 도전해보고자 한다.