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

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

프로그래머스

 

2023.07.15 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 자체는 이해하기 어렵지 않았습니다.

하지만 시간 초과에 계속 막히는 이슈가....

 

시도 1

처음 떠올린 아이디어는 다음과 같습니다.

1. 전체 배열인 stones에서 k길이 만큼의 Sub 어레이를 생성
2. 1에서 생성한 서브 어레이의 최댓값 구하기
3. 1의 작업을 한칸씩 오른쪽으로 이동하며 반복하며 2에서 구한 최댓값들 중에 가장 작은 값을 리턴

원리

k개 이상의 연결된 징검다리가 0 이하로 숫자가 내려가여 더이상 건널 수 없는 상태입니다.

따라서 k 크기의 서브 배열이 전부 0 이하로 내려가야 하는데, 이렇게 되려면 k 크기의 서브 배열의 원소의 최댓값만큼 사람이 지나가야 모든 stone의 숫자가 0 이하가 됩니다.

즉, 각 서브 배열의 요소가 전부 0이 되는 시점은 서브 배열의 최댓값만큼 사람이 지나갔을 경우입니다.

 

코드

fileprivate func solution(_ stones:[Int], _ k:Int) -> Int {
    var result = 200_000_000
    
    for i in 0..<(stones.count-k+1) {
        let subArr = stones[i..<(i+k)]
        let maxStone = subArr.max()!
        result = min(result, maxStone)
    }
    
    return result
}

코드로 구현해 보아도 정말 간단합니다.

k크기의 서브 배열 구하고 최댓값 구하고 비교!

하지만.... 이렇게 하면 시간 복잡도가 O(n^2)이라 시간 초과가 발생했습니다. (for문 안에서 subArry.max()를 실행했기 때문)

 

시도 2

시도 1에서 시간 초과가 발생했기 때문에 기초 아이디어는 유지한채 시간 초과를 해결할 방법을 고민했습니다.

시간 초과의 원인이 subArr.max()를 반복적으로 실행했기 때문이었는데 따라서, 특정 경우에만 최댓값을 찾는 방식을 사용하도록 바꾸었습니다.

 

서브 배열의 크기가 항상 k로 고정이기 때문에 서브 배열의 시작 인덱스를 start, 끝 인덱스를 end로 두고 

start += 1, end += 1 을 수행하며 오른쪽으로 한칸씩 이동하도록 합니다.

 

이때 start를 1 증가시키기 전 start는 서브 배열에서 사라지는 stone의 위치입니다.

따라서 서브 배열의 최댓값을 maxStone이라는 변수에 담고 있다가 사라지는 start 위치가 원래 최댓값(maxStone)이라면 해당 시점에서만 다시 최댓값을 순회하며 구하는 로직입니다.

 

시도1에서는 매번 최댓값을 순회하며 찾았지만 이번에는 start가 기존의 최댓값일 때만 순회하기 때문에 소요 시간을 많이 단축할 수 있습니다.

 

그리고 서브 배열에는 end 위치의 stone이 추가되는데 이렇게 추가되는 stone을 딕셔너리에 저장합니다.

 

최댓값 탐색을 할 때는 이 딕셔너리의 key 값 중에서 max()를 수행하도록 합니다.

 

코드

fileprivate func solution(_ stones:[Int], _ k:Int) -> Int {
    var start = 0
    var end = k - 1
    
    var maxStone = stones[0...k-1].max()!   // 서브 배열의 최댓값
    var result = maxStone
    
    var dict = [Int: Int]() // key: 돌에 적힌 숫자, value: 해당 숫자가 나온 횟수
    
    for i in stones[0...k-1] {
        dict[i, default: 0] += 1
    }
    
    while end < stones.count-1 {
        end += 1
        let endStone = stones[end]
        dict[endStone, default: 0] += 1
        
        maxStone = max(maxStone, endStone)
        
        let startStone = stones[start]
        dict[startStone, default: 0] -= 1
        
        if dict[startStone] == 0 {
            dict.removeValue(forKey: startStone)
            if startStone == maxStone {
                maxStone = dict.keys.max()!
            }
        }
        
        start += 1

        result = min(result, maxStone)
    }
    
    return result
}

처음에는 투 포인터라고 생각하며 코드를 작성했지만 찾아보니 슬라이딩 윈도우 알고리즘(sliding Window Algorithm)의 풀이법이라고 합니다. (특정 범위가 있을 때 윈도우(서브 배열) 내부 요소의 값을 이용하여 문제를 푸는 방식)

 

하지만,,, 채점을 해보니 역시 로직은 맞았으나 효율성 테스트 13번만 통과를 못했습니다.

 

원인을 추측해보면 만약 stones 배열이 다음과 같을 때

[200,000,000, 199,999,999, 199,999,998, ......, 3, 2 , 1]

즉, 내림차순으로 정렬된 배열이 들어왔다면

dict.keys.max()를 매번 수행하게 되어 사실상 첫 번재 풀이법과 동일한 시간 복잡도가 되기 때문입니다.

 

(대신 오름 차순으로 정렬된 데이터가 들어오면 O(n)으로 시간복잡도가 낮아지는 장점이 있습니다.)

 

 

시도 3 - 통과

아예 접근 방식을 바꾸어 이분 탐색을 사용했습니다.

 

징검다리를 건너는 사람을 기준으로

start = 0 명

end = 200,000,000 명

으로 설정한 뒤 이분 탐색을 진행합니다.

 

mid = (start+end)/2 명이고

mid명의 사람이 지나간다는 것은 각 stone에 mid를 뺀 값이 남는다는 의미입니다.

결과적으로 k개 이상의 연결된 stone들이 0 이하로 남았다면 mid명은 해당 징검다리를 건너지 못한다는 의미 입니다.

 

mid명이 못건너면 end를 mid - 1로 설정하여 사람 수를 줄여서 다시 위의 과정을 반복합니다.

mid명이 건널 수 있다면 start를 mid + 1로 설정하여 사람 수를 늘려서 다시 위의 과정을 반복합니다.

 

이렇게 하면 O(n*logN)의 시간 복잡도로 문제를 풀 수 있어서 시간 초과가 발생하지 않습니다.

풀이

fileprivate func solution(_ stones:[Int], _ k:Int) -> Int {
    // 징검다리를 건너는 사람 수로 이분 탐색
    var start = 0
    var end = 200_000_000
    
    while start <= end {
        let mid = (start + end) / 2
        var cnt = 0 // 0 이하가 된 연속되는 돌의 개수
        
        var canMove = true
        for i in 0..<stones.count {
            if stones[i] - mid <= 0 {
                cnt += 1
            } else {
                cnt = 0
            }
            
            if cnt >= k {
                canMove = false
                break
            }
        }
        
        if canMove {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    
    return start
}

기본적인 이분 탐색 풀이법입니다.

 

 

마무리

이분 탐색을 떠올리는 것이 저에게는 아직 쉽지 않은 것 같습니다.

 

처음 떠올린 아이디어가 더 직관적이라고 생각했지만 시간 초과로 인해 오답이 된 것이 아쉽네요..!

슬라이딩 윈도우 + 딕셔너리로 풀었을 때도 특정 케이스에서 시간 복잡도가 O(n^2)이 되는 문제가 있었습니다.

(질문하기 탭을 보니 deque를 사용하면 슬라이딩 윈도우로 풀 수 있다고 하는데 Swift에서는 deque를 직접 구현해야 하기도 하고 해당 풀이법이 이분 탐색보다 더 떠올리기 힘들 것 같아서 그냥 넘어갔습니다.)

 

결론: 이분 탐색을 더 연습해 봐야겠다!