[백준-2805] 나무 자르기

2805 문제는 처음에 굉장히 쉽다고 느껴졌다.

 

이분 탐색법을 적용하는 문제였는데

시간초과를 설명하기 전 이분 탐색법부터 차근차근 설명하도록 하자면

 

이분 탐색법: 탐색 범위를 절반씩 줄여가며 찾아가는 알고리즘으로

경계값이 중간 보다 위에 있다고 판단 된다면 그 (중간값 + 1) ~ 마지막값 에서 다시 탐색을 하고

경계값이 중간 보다 아래에 있다고 판단 된다면 그 반대로 진행되는 것이다

이해가 안간다면

wootool.tistory.com/62

이분의 블로그에 동영상으로 설명하고 있으니 참고하시길 바란다.

 

이렇게 금세 풀었지만 시간 초과라는 결과를 보게되었다.

 

결국 시간문제를 해결 했지만 

 

이처럼 많은 사람들이 이 문제를 겪고 포기한거 같아

 

설명을 하기로 생각했다.

 

우선 readline()에서 대부분 

let input = readLine()!.split(separator: " ").map { Int($0)! }

이렇게 쓸텐데 나와 같은 경우는 이렇게 작성하면 무조건 시간 초과가 보였다.

따라서 아래와 같이 적어야 한다.

let input = readLine()!.split(separator: " ").compactMap{ Int(String($0))}

 

또한 

temp = trees.map { $0 > mid ? $0 - mid : 0 }.reduce(0, +)

이렇게 쓰는 것보다는

func getTree(_ height: Int) -> Int {
  var sum = 0
  for tree in trees where tree > height {
    sum += tree - height
  }
  return sum
}
// 이렇게 함수를 만들어

temp = getTree(mid)
// 이렇게 적용

이렇게 적용하는 것이 빠르다

 

마지막으로 나는 원래 while 문에서 mid와 temp를 let으로 계속 새로 선언했는데

밖으로 변수를 뺀 후 변수에 값을 넣는 형식이 더 빨랐다

 

내 설명이 이해가 잘 안간다면

 

let input = readLine()!.split(separator: " ").compactMap{ Int(String($0))}
let m = input[1]
let trees = readLine()!.split(separator: " ").compactMap{ Int(String($0)) }

var min = 0
var max = trees.max()!
var mid = 0
var result = 0
var temp = 0

while min < max {
  mid = (min + max) / 2
  temp = trees.map { $0 > mid ? $0 - mid : 0 }.reduce(0, +)
  
  if(temp < m) {
    max = mid
  } else {
    result = mid
    min = mid + 1
  }
}

print(result)

완성된 코드를 참고 하기 바란다.