백준 5639(이진 검색 트리)

www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

처음 풀이

/*
    재귀를 이용해서 leftNode에는 subtree의 왼쪽 node들을 저장
    rightNode에는 subtree의 오른쪽 노드들을 저장
    인자로 vector를 전달하기 때문에 메모리 초과 발생
*/
void recursive(vector<int> vec) {
  if(vec.size() == 0) return ;
  int root = vec[0];
  vector<int> leftNode, rightNode;
  for(int idx = 1; idx < vec.size(); idx++) {
    if(vec[idx] < root) leftNode.push_back(vec[idx]);
    else rightNode.push_back(vec[idx]);
  }
  recursive(leftNode);
  recursive(rightNode);
  cout << root << endl;
}

 

정답 코드

vector를 넘기는 대신 왼쪽과 오른쪽 인덱스를 넘겨 구한다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> vec;
void input() {
  int N;
  while(cin >> N) vec.push_back(N);
}

void recursive(int left, int right) {
  int root = vec[left];
  int idx = left + 1;
  for( ; idx <= right; idx++) 
    if(vec[idx] >= root) break;
  if(left < idx - 1) recursive(left + 1, idx - 1);
  if(idx <= right) recursive(idx, right);
  cout << root << endl;
}

int main(void) {
  input();
  recursive(0, vec.size() - 1);
  return 0;
}

 

배열의 양 끝을 left와 right로 잡은 후 root보다 값이 큰 인덱스를 idx변수로 잡아준다.

left + 1에서부터 idx - 1까지가 root의 왼쪽 subtree가 된다.

idx에서부터 right는 root의 오른쪽 subtree가 된다.

위와 같이 진행이 된다.