[2020 KAKAO BLIND RECRUITMENT] 길찾기 게임

풀이1

풀이 2

 

문제는 2번에 걸쳐 풀었다. c++로 푸는데 malloc을 사용하는 것이 맘에 걸려 class에 대한 공부 후 짜보았다. class사용에 조금 더 익숙해질 필요가 있는것 같다.

실행시간차이가 나는것으로 보아 malloc이 느리긴 느린것 같다. 결과를 보니

문제풀이

이진 탐색트리를 만드는 문제이다. BST 연습문제로 좋은 것 같다.

 

풀이1

malloc을 사용한 풀이이다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
typedef struct node *treePointer;
typedef struct node {
    int data;
    int num;
    treePointer leftChild, rightChild;
}node;
treePointer root;
bool cmp(vector<int> a, vector<int> b) {
    return a[1] > b[1];
}
vector<int> prevector;
vector<int> postvector;
void preorder(treePointer ptr) {
    if (ptr) {
        //printf("%d ", ptr->data);
        prevector.push_back(ptr->num);
        preorder(ptr->leftChild);
        preorder(ptr->rightChild);
    }
}
void postorder(treePointer ptr) {
    if (ptr) {
        postorder(ptr->leftChild);
        postorder(ptr->rightChild);
        postvector.push_back(ptr->num);
    }
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    treePointer temp;
    root = (node*)malloc(sizeof(node));
    for (int i = 0; i < nodeinfo.size(); i++) {
        nodeinfo[i].push_back(i+1);
        //cout << nodeinfo[i][2] << endl;
    }
    sort(nodeinfo.begin(), nodeinfo.end(), cmp);
    root->data = nodeinfo[0][0];
    root->num = nodeinfo[0][2];
    root->rightChild = NULL;
    root->leftChild = NULL;
    for (int i = 1; i < nodeinfo.size(); i++) {
        cout << nodeinfo[i][2] << endl;
        temp = (node*)malloc(sizeof(node));
        temp->data = nodeinfo[i][0];
        temp->num = nodeinfo[i][2];
        temp->rightChild = NULL;
        temp->leftChild = NULL;
        for (treePointer cur = root; ;) {
            if (temp->data < cur->data) {
                if (cur->leftChild) {
                    cur = cur->leftChild;
                }
                else {
                    cur->leftChild = temp;
                    break;
                }
 
            }
            else {
                if (cur->rightChild) {
                    cur = cur->rightChild;
                }
                else {
                    cur->rightChild = temp;
                    break;
                }
 
            }
        }
    }
    preorder(root);
    postorder(root);
    answer.push_back(prevector);
    answer.push_back(postvector);
 
 
    return answer;
}
int main() {
    vector<vector<int>> input = { {5, 3}, {11, 5}, {13, 3}, {3, 5}, {6, 1}, {1, 3}, {8, 6}, {7, 2}, {2, 2} };
 
    solution(input);
}

풀이2

tree class를 만들어 푼 풀이이다. 항상 tree구현시 malloc을 사용해 조금더 C++ 처럼 코드를 작성하고자 풀어보았다.

원래 그냥 int 만 사용해도 될것 같았지만 연습삼아 짜보는거라 자바의 제네릭처럼 데이터타입을 지정할수 있도록 작성하였다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
template <typename T>
class Tree;
template <typename T>
class TreeNode {
    friend class Tree<T>;
private:
    TreeNode* leftChild;
    TreeNode* rightChild;
    T data;
    T num;
public:
    TreeNode(T d,T n) {
        data = d;
        num = n;
        leftChild = NULL;
        rightChild = NULL;
    }
};
vector<int> prevector;
vector<int> postvector;
template <typename T>
class Tree {
private:
    TreeNode<T>* root;
public:
    Tree() : root(NULL) {};
    ~Tree() {};
    void insertNode(T data,T num) {
        TreeNode<T>* node = new TreeNode<int>(data,num);
        //NULL이 아니면 중복된 값이 입력되는거임
        if (root == NULL) {
            root = node;
            return;
        }
        TreeNode<T>* parent = NULL;
        for (TreeNode<T>* cur = root;;) {
            if (node->data < cur->data) {
                if (cur->leftChild) {
                    cur = cur->leftChild;
                }
                else {
                    cur->leftChild = node;
                    break;
                }
            }
            else {
                if (cur->rightChild) {
                    cur = cur->rightChild;
                }
                else {
                    cur->rightChild = node;
                    break;
                }
            }
        }
    }
    void preorder(TreeNode<T>* ptr){
        if (ptr) {
            //printf("%d ", ptr->data);
            prevector.push_back(ptr->num);
            preorder(ptr->leftChild);
            preorder(ptr->rightChild);
        }
    }
    void postorder(TreeNode<T>* ptr) {
        if (ptr) {
            postorder(ptr->leftChild);
            postorder(ptr->rightChild);
            postvector.push_back(ptr->num);
        }
    }
    TreeNode<T>* getRoot() {
        return root;
    }
    
};
bool cmp(vector<int> a, vector<int> b) { //내림차순 y축기준
    return a[1] > b[1];
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    for (int i = 0; i < nodeinfo.size(); i++) {
        nodeinfo[i].push_back(i + 1);//node value 추가
    }
    sort(nodeinfo.begin(), nodeinfo.end(), cmp);
    Tree<int>* bst = new Tree<int>();
    for (int i = 0; i < nodeinfo.size(); i++) {
        bst->insertNode(nodeinfo[i][0],nodeinfo[i][2]);
    }
    bst->preorder(bst->getRoot());
    answer.push_back(prevector);
    bst->postorder(bst->getRoot());
    answer.push_back(postvector);
    return answer;
}
int main() {
    vector<vector<int>> input = { {5, 3}, {11, 5}, {13, 3}, {3, 5}, {6, 1}, {1, 3}, {8, 6}, {7, 2}, {2, 2} };
    solution(input);
}

 

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

프로그래머스