[카카오 코딩 테스트] 길 찾기 게임

https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

처음에 엄청 복잡하게 생각해서 여러 시행착오를 겪은 문제입니다.. ㅠㅠ 

tree를 vector double array로 만들수 있다고 생각했던게 문제였네요

 

단순하게 생각하면 오히려 쉽게 해결할 수 있는 문제였습니다. 

1. 정렬을 합니다! -> y가 큰 순서, 그다음은 x가 작은 순서

2. 그 순서대로 tree에 넣어줍니다.

  2-1. bst처럼 부모노드보다 작으면 left, 크면 right child로 재귀형태로 넣어줍니다.

3. preorder, postorder 수행 

끝!

 

간만에 포인터를 활용해봤네요.

이런 tree문제를 제가 많이 접하지 못해서 해결에 애를 먹었던 것 같습니다.. ㅠㅠㅠㅠ

 

쨋든!

아래는 풀이한 코드입니다:)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> answer(2);
struct NodeInfo{
    int x, y, n; // n = 노드번호
};
 
struct Tree {
    NodeInfo node;
   Tree *left;
   Tree *right;
};
 
bool cmp(NodeInfo a, NodeInfo b) {
    if (a.y > b.y) return true;
    else {
        if (a.y == b.y && a.x < b.x) return true;
        else return false;
    }
}
 
// 작으면 왼쪽노드, 크면 오른쪽노드에 넣기
void add(Tree *&t, Tree *tmp) {
    if (t == NULL) {
        t = tmp;
        return;
    }
    if (tmp->node.x < t->node.x)
        add(t->left, tmp);
    else
        add(t->right, tmp);
}
 
void preorder(Tree *t) {
    if (t != NULL) {
        answer[0].push_back(t->node.n);
        preorder(t->left);
        preorder(t->right);
    }
}
void postorder(Tree *t) {
    if (t != NULL) {
        postorder(t->left);
        postorder(t->right);
        answer[1].push_back(t->node.n);
    }
}
 
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
 
    // 뒤죽박죽인 노드 정보들을 y를 기준으로 내림차순 정렬
    vector<NodeInfo> nodes;
    for (int i = 0; i < nodeinfo.size(); i++) 
        nodes.push_back({nodeinfo[i][0],nodeinfo[i][1],i+1});
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    // Tree에 노드 넣기!
    // 최 상단 노드부터(부모) 차례대로
   Tree *t = new Tree;
    t->node = nodes[0];
    t->left = NULL;
    t->right = NULL;
    for (auto node : nodes) {
        if (node.n == nodes[0].n) continue;
       Tree *tmp = new Tree;
        tmp->node = node;
        tmp->left = NULL;
        tmp->right = NULL;
        add(t, tmp);
    }
    preorder(t);
    postorder(t);
    return answer;
}
 
int main() {
    vector<vector<int>> result = solution({ 
{5, 3},{11, 5},{13, 3},{3, 5},
{6, 1},{1, 3},{8, 6},{7, 2},{2, 2} });
    for (auto x : result) {
        for (auto y : x)
            cout << y << ' ';
        cout << endl;
    }
    return 0;
}