[c++]백준 5639 - 이진 검색 트리

0. [c++] 백준  -

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

1. 풀이

이진검색트리를 활용해서 문제를 풀어보았다.

우선, 이진 검색 트리를 만들어보고, 이를 활용해서 문제를 풀어보았다.

+) 이후에 굳이 트리를 만들지 않고도 문제해결이 가능하여 더 쉬운 방법도 활용해보았다.

입력을 보면 가장 처음 들어온 50을 기준으로 45까지는 왼쪽 트리, 98,54,60은 오른쪽 트리에 속하게 된다.

이런 쪼개기를 확확 해주면 답을 구할 수 있다.

약간 bfs느낌?

2. 소스코드

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

#include<iostream> #include<algorithm>   using namespace std;   struct Node {     int value, depth;     //두 자식 노드의 포인터     Node* left, *right;     Node(const int& _value) : value(_value), depth(0), left(NULL), right(NULL) { }     void setLeft(Node* newLeft) { left = newLeft;}     void setRight(Node* newRight) { right = newRight;} };   Node* insert(Node* root, Node* node) {     if (root == NULL) return node;     if (node->value < root->value)         root->setLeft(insert(root->left, node));     else         root->setRight(insert(root->right, node));     return root; }   void printNode(Node* node) {     if (node->left != NULL)         printNode(node->left);     if (node->right != NULL)         printNode(node->right);     printf("%d\n", node->value);      }   int main() {     int temp;     Node* Nodes = NULL;     while(scanf("%d", &temp) != EOF) {         Nodes = insert(Nodes, new Node(temp));     }     printNode(Nodes);   } Colored by Color Scripter

cs

+)

#include <iostream>
#include <algorithm>
using namespace std;
int Arr[10002];
 
void printNode(const int& left, const int& right) {
    if (left > right) return;
    
    int root = Arr[left];
    int last = right;
    while (Arr[last] > root) last--;
    //Arr[left]를 부모 노드로 하고 두 가지로 나뉜다.
    //왼쪽 노드가 되고
    printNode(left + 1, last);
    //오른쪽 노드가 된다.
    printNode(last + 1, right);
    //자신은 출력해주자.
    printf("%d\n", root);
}
 
int main() {
    int temp;
    int N = 0;
    while (scanf("%d", &temp) != -1) Arr[N++] = temp;
    printNode(0, N-1);
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!