[Algorithm/Swift] 프로그래머스(Lv.3) - 징검다리 건너기

안녕하세요 제인입니다:) 

PS로 하루를 힘차게 시작하려고 했는데 이제 할 일을 좀 하고 문제를 풀어야겠어요...ㅇ<-<

오늘 저를 괴롭힌 문제를 보시죠 징검다리 건너기 레쭈고.

문제 링크

프로그래머스

문제 풀이

처음 풀이

투 포인터 활용 (테스트케이스 모두 통과, but 효율성 0점)

import Foundation

func solution(_ stones:[Int], _ k:Int) -> Int {
    var pointer1 = 0, pointer2 = k-1
    var max = Int.max // 길이 k인 구간에서의 최댓값 저장

    while pointer2 < stones.count {
        let maxElement = stones[pointer1...pointer2].max()!
        if max > maxElement { max = maxElement }
    
        pointer1 += 1
        pointer2 += 1
    }

    return max
}

 

처음에는 투 포인터를 활용해 슬라이딩 윈도우 기법으로 k개의 디딤돌을 한 구간으로 설정해서 전체를 스캔하는 방식으로 풀었습니다.

왜냐하면, 징검다리를 더 이상 건너지 못하게 되는 순간은 적힌 숫자가 0이 되는 디딤돌이 k개 연달아 나오는 경우이기 때문에 길이가 k인 구간 안에서의 최댓값이 해당 구간을 건널 수 있는 사람의 최대 숫자라는 것을 파악했고, 항상 가장 가까운 돌을 밟아야 하므로 한 사람이 건널 때마다 전체 돌의 숫자가 1씩 감소하기 때문에 전체 다리를 건널 수 있는 사람의 최대 숫자를 구하기 위해서는 한 구간 내의 최댓값을 저장하면서 더 작은 최댓값이 나오면 갱신해주는 방법(최댓값들 중 최솟값이 최종 답)으로 최종 값을 구할 수 있겠다고 생각했습니다.

 

이러한 아이디어는 맞았던 것 같은데, 전체 다리를 스캔하는 과정에서 구간 내의 최댓값을 찾기 위해 매번 전체 배열을 k만큼 슬라이스해서 길이가 k인 새로운 배열을 생성하게 되기 때문에 시간 복잡도가 O(k)가 되어 전체 배열의 길이가 길다면 비효율적인 탐색 방식이 됩니다. (이 문제의 경우 stones 배열의 크기가 최대 200,000입니다.)

 

효율성을 어떻게 개선할까.. 하다가 이전에 배열에 요소를 계속 추가해주면서 최댓값 or 최솟값을 업데이트 해주어야 할 때 우선순위 큐를 활용한 기억이 있어서 힙을 구현해서 개선해보자! 라는 아이디어가 떠올랐지만, 우선순위 큐의 크기를 계속 k로 유지하기 위해서는 전체 배열을 순회하며 새로운 값을 insert해줄 때 배열의 바로 이전 인덱스의 요소를 우선순위 큐에서 삭제해주어야 하는데, 우선순위 큐에서는 특정 원소를 찾아서 remove 연산을 해줄 수가 없기 때문에 (우선순위 큐의 원소는 insert, remove해줄 때마다 순서가 바뀌기 때문에 removeFirst()로는 이전 삽입 값 삭제 불가) 이 방법으로는 개선할 수 없겠구나..를 깨닫고 다른 풀이를 찾아보았습니다.. 

최종 풀이

다른 블로그들의 풀이를 참고한 결과, 이분 탐색 알고리즘을 사용해서 문제를 해결할 수 있었습니다. (이분 탐색은 생각지도 못했어요)

건널 수 있는 사람의 수를 반으로 줄여가면서 확인하는 방식으로 최적의 해를 찾아내는 방식이었는데요, 이분 탐색을 이용한 풀이 과정은 다음과 같습니다.

1. left와 right를 각각 stones 배열의 원소가 될 수 있는 최솟값과 최대값으로 초기화합니다. (left = 1, right = 200000000)
2. mid명의 사람이 징검다리를 건널 수 있는지 확인해봅니다.
3-1. 2의 과정에서 건널 수 있으면 mid명 이상의 범위를 탐색하면 되므로 left 값을 mid+1로 바꿉니다.
3-2. 2의 과정에서 건널 수 없다면 right 값을 mid명 이하의 범위를 탐색하면 되므로 mid로 바꿉니다.
4. 건널 수 있는 최대 명수를 구해야 하므로, left < right 인 동안 위의 과정을 반복합니다. 

Swift 풀이 코드

import Foundation

func solution(_ stones:[Int], _ k:Int) -> Int {
    var left = 1
    var right = 200000000
    
    while left < right {
        let mid = (left + right) / 2
        var skipCount = 0 // 건너뛰어야하는 돌의 개수
        
        for i in 0..<stones.count {
            if stones[i] - mid <= 0 { // 점수 0 이하로 떨어지는 곳 생기면
                skipCount += 1
                
                if skipCount >= k { // 점수 0되는 곳이 연달아 k개 이상 나오면
                    break // 반복문 탈출
                }
            } else { // mid명만큼 건널 수 있으면
                skipCount = 0 // skipCount 초기화
            }
        }
        
        // 가능 여부에 따라 left, right 다시 설정
        if skipCount >= k { // mid명 건널 수 없으면 mid명 이하의 범위를 탐색
            right = mid
        } else { // mid명 건널수 있으면 mid명 이상의 범위를 탐색
            left = mid + 1
        }
    }
 
    return left
}

 

---

[참고 자료]

[Swift 알고리즘] 프로그래머스(Lv.3) - 징검다리 건너기 / 2019 카카오 인턴십

프로그래머스: 징검다리 건너기 - Swift

[알고리즘 문제 풀이] 프로그래머스 징검다리 건너기