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

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 징검다리 건너기" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 징검다리 건너기

 

---

풀이

이번 문제는 이분 탐색 문제입니다.

 

푸념

1시간정도 고민하다 풀이를 보고 해결했는데요.(코드 작성은 직접... ㅎ)

처음에는 보고도 왜 이분 탐색인지 이해가 안 갔습니다.

시간복잡도 시선이 아닌 이 문제를 보고 어떻게 이분 탐색을 떠올릴 수 있지? 라는 생각을 했던 것 같습니다.

 

제가 처음 접근한 방법은 최장 감소 수열같은 로직이었습니다.

연속된 0의 개수가 k가 되면 건널 수 없으니 위와 같은 아이디어를 떠올렸는데요.

문제는 최대 몇 명까지 건널 수 있는지 구하는 것이 어려웠습니다.

 

사실 여기에서 이분 탐색을 떠올리지 못한건 경험 부족이겠죠?

포스팅을 쓰다보니 "최대 몇 명", "최대 2억" 등을 보고 충분히 유추할 수 있었겠네요..

 

본론

본론으로 돌아가서 이 문제는 이분 탐색입니다.

1억으로 시작하여 건널 수 있으면 인원을 늘려서, 건널 수 없으면 인원을 줄여서 다시 탐색 합니다.

 

건널 수 없음을 판단하는 방법은 0의 연속된 개수를 이용합니다.

stones의 숫자 - 건너는 인원 mid가 0 미만이면 count를 늘려줍니다.

 

연속으로 count가 k개 이상 늘어나면 건널 수 없습니다.

건널 수 없다면 right를 mid로 설정하여 인원수를 줄입니다.

 

반대로 연속으로 count가 k개 이상 늘어나는 경우가 없다면 건널 수 있습니다.

건널 수 있다면 left를 mid+1로 설정해 인원수를 늘여서 확인합니다.

 

최종적으로 left가 right보다 커질 때 탐색을 완료하며 이때 구해진 left가 건널 수 있는 최대 인원입니다.

 

감사합니다!

---

전체 코드

import Foundation

func solution(_ stones:[Int], _ k:Int) -> Int {
    var left = 1
    var right = 200000000
    
    while left < right {
        let mid = (left + right) / 2
        var count = 0
        for i in 0..<stones.count {
            if stones[i] - mid <= 0 {
                count += 1
                
                if count >= k {
                    break
                }
            } else {
                count = 0
            }
        }
        
        if count >= k {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.