문제 푼 날짜 : 2021-07-09

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42892

접근 및 풀이

주어진 입력값을 이용하여 트리형태로 표현하고, 전위 순회(Preorder)와 후위 순회(Postorder)를 구현하는 문제였다.
트리를 구현함에 있어서 아래와 같이 주어진 조건에 맞게 구현하면 된다.

1. 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
2. 모든 노드는 서로 다른 x값을 가진다.
3. 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
4. 자식 노드의 y 값은 항상 부모 노드보다 작다.
5. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
6. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

순회를 하기 위해서는 루트 노드를 결정하는 게 가장 중요하다고 생각했다.
문제에 주어진 그림을 보면 7번 노드가 루트 노드인데, y값이 가장 큰 것을 알 수 있다.
따라서 주어진 1~n번까지의 노드들의 정보를 y값이 큰 순서대로 정 만약 같다면 x값이 작은 순으로 정렬했을 시에, 맨 처음에 위치하는 노드가 루트노드일 것이다.
이를 이용해서 트리를 구성해주고 전위 순회와 후위 순위를 한 결과 값을 return 해주었다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    int num, x, y;
    Node* left;
    Node* right;
};

bool compare(Node n1, Node n2) {
    if (n1.y == n2.y) {
        return n1.x < n2.x; // y값이 같다면 x값이 작은 순으로 정렬
    }
    return n1.y > n2.y; // y값이 큰 순으로 정렬
}

void makeTree(Node *root, Node *child) {
    if (root->x > child->x) { // x 값이 작으면 왼쪽 자식
        if (root->left == NULL) {
            root->left = child;
        } else {
            makeTree(root->left, child);
        }
    } else { // x 값이 크다면 오른쪽 자식
        if (root->right == NULL) {
            root->right = child;
        } else {
            makeTree(root->right, child);
        }
    }
}

void preorder(vector<int> &v, Node *root) { // 전위 순회
    if (root == NULL) {
    	return;
    }
    v.push_back(root->num);
    preorder(v, root->left);
    preorder(v, root->right);
}

void postorder(vector<int> &v, Node *root) { // 후위 순회
    if (root == NULL) {
    	return;
    }
    postorder(v, root->left);
    postorder(v, root->right);
    v.push_back(root->num);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer = {{}, {}};
    vector<Node> node;
    
    for (int i = 0; i < nodeinfo.size(); i++) {
        node.push_back({ i + 1, nodeinfo[i][0], nodeinfo[i][1] });
    }
    sort(node.begin(), node.end(), compare);
    
    Node *root = &node[0];
    
    for (int i = 1; i < node.size(); i++) {
        makeTree(root, &node[i]);
    }
    preorder(answer[0], root);
    postorder(answer[1], root);
    
    return answer;
}

결과

피드백

주어진 인풋을 이용해 트리를 구성하여 푸는 문제도 자주 나오는 문제유형인 것 같다.
트리 문제도 많이 풀어서 익숙해지는 연습을 해야할 것 같다.