BOJ5639: 이진 검색 트리

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

  • 이진탐색으로 풀었는데, 이진탐색 안해도 풀림. 다음 수가 Bound보다 크면 탈출하는 식으로 Bound를 주면, 탐색 없이 가능
  • 여튼 이진탐색으로 풀면서 얻은 몇가지 교훈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 이런식으로 두면 s ~ e-1까지 조회함
// lb나 ub는 결국 같아지고, s~e까지의 값이 나올 수 있음.
int lb = s, ub = e;
while(lb < ub) {
  int m = (lb + ub) / 2;
  if(preOrder[m] > root) ub = m;
  else lb = m+1;
}

// 마찬가지로 s ~ e-1까지 조회함
// 까다로운 부분은 lb를 s-1로 두어야 함.
// lb와 ub는 1차이나는 상태로 멈추게 됨.
// ub를 답으로 쓸것이기 때문에, ub가 s~e까지 멈출수 있게 하려면 아래와 같이 두어야 함.
int lb = s-1, ub = e;
while(lb + 1 != ub) {
  int m = (lb + ub) / 2;
  if(preOrder[m] > root) ub = m;
  else lb = m;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;


class Problem {
  vector<int> preOrder;
public:
  void input();
  void dfs(int s = -1, int e = -1);
};

void Problem::input() {
  int tmp;
  while(cin >> tmp)
    preOrder.push_back(tmp);
}

void Problem::dfs(int s, int e) {
  if (s == -1) s = 0;
  if (e == -1) e = preOrder.size();
  if (s == e) return;
  int root = preOrder[s];
  if (s+1 == e) {
    printf("%d\n", root);
    return;
  }

  int lb = s+1, ub = e;
  while(lb < ub) {
    int m = (lb + ub) / 2;
    if(preOrder[m] > root) ub = m;
    else lb = m+1;
  }
  dfs(s+1, ub);
  dfs(ub, e);
  printf("%d\n", root);
}

int main() {
  Problem problem;
  problem.input();
  problem.dfs();
}