백준 5639 이진 검색 트리

출처: www.acmicpc.net/problem/5639

분류: 트리

---

접근방식

pre-order 결과가 들어오면 이 트리의 post-order 검색의 결과를 출력하는 문제였습니다.

pre-order의 결과를 놓고 보면

첫 번째가 root, 
root+1 부터 처음으로 root보다 큰 값이 나오는 위치까지가 Left
그 다음이 Right 트리가 됩니다.

 

우리가 원하는 결과인 post-order는 왼쪽부터 탐색하기 때문에

루트를 타겟으로 이분탐색으로 UpperBounds를 찾아서 

왼쪽 -> 오른쪽 -> 루트 

를 반복적으로 돌려주면 원하는 결과를 얻을 수 있습니다.

 

처음엔 입력 받을 때마다 루트부터 위치를 찾아 트리를 만들어 나가는 방식으로 접근했었는데 이렇게 하니까 시간초과가 났습니다.
c++로는 이런 식으로 풀어도 통과가 되는 것 같던데 swift는 안 되는건지 제가 뭔갈 잘못했던 것인지를 모르겠네요.. 😢

해결방법

 

import Foundation

var preOrderList = [Int]()
while let s = readLine(), let n = Int(s) {
  preOrderList.append(n)
}

func binaryUpperBounds(start: Int, end: Int, target compare: Int) -> Int {
  var start = start
  var end = end

  while start < end {
    let mid = (start + end)/2

    if compare < preOrderList[mid] {
      end = mid
    } else {
      start = mid+1
    }
  }
  return start
}

func postOrder(start: Int, end: Int) {
  guard start < end else { return }

  let upperIndex = binaryUpperBounds(start: start+1, end: end, target: preOrderList[start])
  postOrder(start: start+1, end: upperIndex)
  postOrder(start: upperIndex, end: end)
  print(preOrderList[start])
}

postOrder(start: 0, end: preOrderList.count)

 

배운점

어렵지 않은 문제였는데 이걸로 몇 시간을 날린지 모르겠다...

트리를 만들어 나가는 방식으로 했다가 시간초과를 맞고,

마지막까지 입력받은 트리를 currentNode로 두고 다음 위치를 찾아 막 비교해보는 방식으로 하려고도 해봤는데;;
이런 식으로는 현재 노드가 트리의 어느 부분인지 감을 잡을 수 없기 때문에 도저히 찾을 수가 없는 것 같다.... 여기서 얼마나 헤맨건지...

고통스럽다...