M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 12767 - Ceiling Function

최대 1 분 소요

문제

백준 12767 - Ceiling Function 풀러가기

문제 풀이

주어진 입력들로 만들 수 있는 서로 다른 binary search tree의 형태 수를 찾는 문제다.

  1. 주어진 문제로 binary search tree를 만든다.
  2. 순회 한 결과가 몇개가 있는지 확인하면 된다. 여기선 pre-order로 구현했다.

문제 코드(C++)

  1. 전체 코드

    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
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    #include <cstdio>
    #include <set>
    #include <vector>
    #include <string>
     
    using namespace std;
     
    struct Node {
        int val;
        Node* left;
        Node* right;
        Node() {
            val = 0;
            left = NULL;
            right = NULL;    
        }
    };
     
    string preorder(Node *root) {
        string ans = "";
        ans += "V";
        if (root->left) {
            ans += "L";
            ans += preorder(root->left);
            ans +="l";
        }
        if(root->right) {
            ans += "R";
            ans += preorder(root->right);
            ans += "r";
        }
        ans += "v";
        return ans;
    }
     
    void remove(Node *root) {
        if (root->left) {
            remove(root->left);
        }
        if (root->right) {
            remove(root->right);
        }
        delete root;
    }
     
    int main() {
        int n, k;
     
        scanf("%d %d", &n, &k);
     
        set<string> s;
     
        while (n--) {
            vector<int> a(k);
            for (int i = 0; i < k; i++) {
                scanf("%d", &a[i]);
            }
     
            Node* root = new Node;
            root->val = a[0];
            for (int i = 1; i < k; i++) {
                Node* curr = root;
                while (1) {
                    if (curr->val > a[i]) {
                        if (curr->left == NULL) {
                            curr->left = new Node();
                            curr->left->val = a[i];
                            break;
                        }
                        else {
                            curr = curr->left;
                        }
                    }
                    else if (curr->val < a[i]) {
                        if (curr->right == NULL) {
                            curr->right = new Node();
                            curr->right->val = a[i];
                            break;
                        }
                        else {
                            curr = curr->right;
                        }
     
                    }else{
                        break;
                    }
                }
            }
            s.insert(preorder(root));
            remove(root);
        }
        printf("%d", s.size());
        return 0;
    }
    		cs
    • 54 ~ 88번째 줄 : 주어진 input 배열로 bst를 만든다. 현재 노드보다 값이 작다면 왼쪽에, 오른쪽에 값을 넣는다. 왼쪽이나 오른쪽에 이미 값이 있다면 그 노드로 이동하여, 해당 노드의 자식이 있는지를 파악한다. * 19~34번째 줄 : preorder로 순서를 찾는다. 방문했을 때 V, L, R 방문을 끝내고 나갈 때를 v,l,r로 표시했다.
    • 89번째 줄 : preorder 함수에서 구한 값을 set에 넣어준다. set은 중복이 없는 값으로 구성된다.





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고