[백준/Swift] 17266 : 어두운 굴다리

안녕하세요!!

---

https://www.acmicpc.net/problem/17266

17266번: 어두운 굴다리

간단하게 문제 설명하겠습니다.

'겁쟁이 상빈이' 를 위해 어두운 굴다리( 0 ~ N 길이)가  "가로등"에 의해 길이 모두 밝게 비춰지도록 가로등을 설치해야한다.

이때 가로등의 높이는 갖고, 가로등의 높이만큼 좌, 우 거리가 밝게 빛난다.

"길을 모두 비추는 " 최소한의 가로등 높이는?

 

예제 그림과 같이 

굴다리 길이 0~ N일 경우

가로등의 위치는 2, 4이다.

 

이때 가로등의 높이가 1인 경우 0~1의 길이 비춰지지 않아 상빈이는 통과할 수 없다! (== 가로등의 높이가 1보다는 커야한다. )

입력값은 아래와 같이 주어집니다.

이분탐색을 활용해 풀 수 있는 문제입니다.

단순하게 반복문을 사용해서 1부터 n까지 높이를 구할 수 있지만, 시간복잡도는 포문의 1~n까지 완전 탐색을 해야하므로 시간 복잡도는

O( n )이 걸립니다.

반면에 이분 탐색을 활용하면 답을 찾을 확률은 O(log n)입니다. 

 

이분 탐색 설명 간단 예시

1 ~ 100까지의 자연수 중에서 75번째 자연수를 찾는 방법은 1부터 75번째까지 포문을 75번만 돌리면 됩니다.

이분 탐색의 경우 차례대로 순회하지 않고 '중간값'을 정해가면서 특정한 자연수를 찾는 방 법입니다.

50 -> 75 ( 단 두번만에 찾을 수 있습니다)

- TMI - 알고리즘에서 log n 은 밑이 10이 아닌 2를 의미합니다. log 2  n < 컴퓨터가 이진수 시스템을 사용하기 때문에 ... >

 

따라서 문제를 풀 때 이분 탐색을 활용해서 가로등의 높이를 정하는 방법을 사용했습니다.

( 오른쪽의 case 0~ case3까지는 isAllShine() 함수의 작업을 통해 알 수 있습니다. ( 특정 높이가 모든 길을 비추는가?)

 

이 경우에는 가로등 높이가 2일때 길들은 모두 훤하게 비춰집니다. 

 

물론 3일때는 당연히 이전 가로등 높이가 2일때 모든 길을 비췄으니 당연히 만족을 합니다. 

2 이상의 높이는 탐색할 필요가 없습니다.

 

이제 남은건 2보다 작은 높이들 중 최소한의 높이로 모든 길을 비추는 높이가 있는지 판단하면 됩니다. 

역시 이 값도 이분 탐색을 통해 mid를 구한 후 최소한의 높이로 모든 길을 비추는지?의 유무를 파악한 후 있다면 그 값이 '2'보다 더 작은 높이의 가로등이 되는 것 입니다.

while(left <= right){
	mid = (left + right) / 2
    if (isAllShine(height: mid)){ // isAllShine은 특정 높이가 모든 길을 비추는지 탐색하는 함수
    	answer = mid
        right = mid - 1
    }else{
        left = mid + 1
	}
}

 

---

다음은 코드입니다.

import Foundation

/**
 * @param : n = 굴다리 개수
 * @param : m = 가로등 개수
 * @param : location = 가로등 위치
 */
var n = Int(readLine()!)!
var m = Int(readLine()!)!
var location = readLine()!.split(separator: " ").map{Int(String($0))!}

/**
 * 이진 탐색을통한 최소 높이 탐색 함수
 *****
 * @param left : 좌
 * @param right : 우
 * @param mid : ( left + right ) / 2
 * 만약 left 가 right 보다 큰 값이라면? 무한 루프 탈출 후 결과 출력.
 */
func binary_search(){
    var left = 0
    var right = n
    var mid = 0
    var answer = 0
    while(left <= right){
        mid = (left + right) / 2
        if (isAllShine(height: mid)){
            answer = mid
            right = mid - 1
        }else{
            left = mid + 1
        }
    }
    print(answer)
}
// 주어진 높이 height가 모든 길을 비추는가? == true !
func isAllShine(height : Int) -> Bool{
    var lightCount = 0
    
    for streetLampIndex in location {
        if streetLampIndex - height <= lightCount {
            lightCount = streetLampIndex + height
        }else{
            return false
        }
    }
    if lightCount >= n{
        return true
    }else{
        return false
    }
}

binary_search()

긴 글 읽어주셔서 감사합니다!