BOJ2379: 트리 탐색하기

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

  • 제대로된 구조화 아이디어를 떠올리는게 어려웠다.
  • 첫 아이디어
    • 일단 처음에는 recursive로 subtree들을 순회하면서 subtree에 해당하는 문자열을 정렬했다.
    • 맞긴 맞지만, 최악의 경우 N^2이 되는 안좋은 구현이다.
  • 다른 사람의 풀이를 보고 다시 풀었음
    • 핵심은 모든 SubTree의 사이즈를 다 알고 있으면, 트리를 복구해 낼 수 있다는 사실을 아는것이다.
    • 즉 모든 노드에 대해서 subTree의 사이즈를 구해 배열에 넣고, 이걸 정렬한 뒤 비교하면 된다.
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
#include <bits/stdc++.h>
using namespace std;

class Organizer {
  void input();
public:
  vector<int> solve();
};

vector<int> Organizer::solve() {
  string s;
  cin >> s;
  stack<int> st;
  vector<int> ans;
  for(int i = 0; i < s.size(); i++) {
    if(s[i] == '0') st.push(i);
    else {
      int treeSize = (i - st.top() + 1) / 2;
      ans.push_back(treeSize);
      st.pop();
    }
  }
  sort(ans.begin(), ans.end());
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  int TC;
  cin >> TC;
  while(TC--) {
    Organizer A, B;
    vector<int> a = A.solve();
    vector<int> b = B.solve();
    printf("%d\n", (a == b));
  }
}