[Swift] 2019 KAKAO WINTER INTERNSHIP 징검다리 건너기

 

Problem

 

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

---

Solution

 

해당 문제는 이진탐색으로 풀어야 하는 문제입니다.

 

1. stones의 숫자를 오름차순 정렬한 뒤 중복 숫자를 제거한다.

 

stones를 Set로 만들고 sorted 메소드로 정렬해줍니다. (sort라고 부르겠습니다.)

 

(ex [1,1,5,3,2,2] -> [1,2,3,5])

 

2. 건널 수 있는지 없는지 체크합니다.

 

0이하의 숫자의 연속된 갯수가 k보다 같거나 크다면 건널 수 없는 징검다리입니다.

 

(ex [-1, 0, -2, 1, 0] -> 연속된 0이하 갯수는 3)

 

3. sort를 이진탐색 

 

이진 탐색으로 sort안의 숫자 중 건널 수 있는 가장 최대의 값을 알아냅니다.

---

Source Code

 

	import Foundation
	func solution(_ stones:[Int], _ k:Int) -> Int {
	return binarySearch(stones: stones,k: k)
	}
	func binarySearch(stones:[Int],k:Int) -> Int {
	let sort = Set(stones).sorted()
	var maxCount:Int = 0
	var min = 0
	var max = sort.count
	while min <= max {
	let mid = (min + max) / 2
	let newStones = stones.map{$0 - sort[mid]}
	if !isCrossable(stones: newStones, k: k) {
	maxCount = mid
	max = mid - 1
	} else {
	min = mid + 1
	}
	}
	return sort[maxCount]
	}
	func isCrossable(stones:[Int],k:Int) -> Bool {
	var counts = Array(repeating: 0, count: stones.count)
	for (i,stone) in stones.enumerated() {
	if stone < 1 {
	counts[i] = i == 0 ? 1 : counts[i-1] + 1
	}
	if counts[i] == k {
	return false
	}
	}
	return true
	}

view raw 징검다리 건너기.swift hosted with ❤ by GitHub