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

문제 설명

 

징검다리를 한 번 건널 때마다 해당 돌의 숫자가 -1된다.
한 친구가 왼쪽에서 오른쪽에서 모두 건너면 다음 친구가 건넌다.
돌의 숫자가 0이되면 더 이상 밟을 수 없고 다음 칸으로 k칸만 넘어갈 수 있다.
만약 k칸 넘게 넘어야 하는 상황이면 그 친구는 넘어가지 못한다.
최대 몇명까지 징검다리를 건널 수 있을까?

 

 

위의 예시에선 k가 3이다. 따라서 최대 3칸을 건너뛸 수 있다.

 

문제 풀이

첫번째 풀이

처음엔 그대로 구현해서 풀어봤다.

무한 루프를 돌면서 한 친구가 건널 때마다 0의 개수를 세어주고
만약 0이 개수가 k보다 같거나 크면 멈추고 건넌 친구의 개수를 세는 방식으로 구현해보았다.

func solution(_ stones:[Int], _ k:Int) -> Int {
    var stones = stones
    var answer = 0 // 건넌 친구의 수
    
    while true {
        var zeroCount = 0
        for i in 0..<stones.count {
            if stones[i] == 0 { // 돌의 숫자가 0이면 zeroCount +1
                zeroCount += 1
            } else { // 돌의 숫자가 0이 아니면 zeroCount는 다시 0부터 셈
                zeroCount = 0
            }
            if zeroCount >= k {
                break
            }
            stones[i] = stones[i] > 0 ? stones[i]-1 : 0
        }
        if zeroCount >= k {
            break
        }
        answer += 1
        
    }
    
    return answer
}

정확성 테스트는 통과했으나 효율성에서 탈락 ㅠ

효율성에서 시간 초과..ㅠㅠ

 

 

 

두번째 풀이

제한사항 : stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.

 

이 문제는 이분탐색으로 효율성을 통과하는 문제였다. 

위에 제한사항을 통해 건널 수 있는 최대 친구를 이분탐색으로 구한다.

 

func solution(_ stones:[Int], _ k:Int) -> Int {
    var left = 1, right = 200000000
    
    while left <= right {
        let mid = (left+right)/2
        var zeroCount = 0 // 숫자가 0인 돌의 개수
        for i in 0..<stones.count {
            if stones[i] - mid <= 0 { // (돌의 숫자-친구의수)가 0보다 작을 때
                zeroCount += 1
            } else {
                zeroCount = 0
            }
            if zeroCount >= k {
                break
            }
        }
        if zeroCount >= k {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return left
}

left는 1, right는 20000000으로 잡는다. (right를 stones.max()로 구하면 시간초과남)

 

(돌의 숫자 - mid)가 0보다 작거나 같으면 그 돌의 숫자는 0이므로 숫자가 0인 돌의 개수를 +1해준다.

만약 숫자가 0인 돌의 개수가 k와 같거나 크면 현재 친구의 수(mid)로는 못건너기때문에 right를 mid-1로 옮겨준다.

현재 친구 수(mid)로 건널 수 있으면 left를 mid+1로 옮겨준다.

 

 

통과