[프로그래머스] 길 찾기 게임

2019 카카오 채용 코딩 테스트 문제입니다.

코딩테스트 연습 - 길 찾기 게임

문제 확인

 

이진트리 문제입니다.

 

풀이

 

포인터를 활용하는 것보다 인덱싱을 사용하는 것이 더 빠르므로 이를 사용합니다.

가로의 값 y는 중복될 수 없으므로 이를 이용하여 삽입할 노드의 y값이 현재 노드 y값보다 작으면 왼쪽, 크면 오른쪽 자식 노드로 넘기며 선택 위치가 빈칸인 경우 해당 위치에 삽입합니다.

 

프리오더, 포스트 오더를 한번에 재귀를 사용하지 않고 구현하기 어려우므로 간단하게 재귀 함수를 이용해 순회합니다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
 
typedef struct node{
    int x, y, idx;
    int left, right;//포인터 대신 인덱싱
}node;
node ary[10001];
 
void travl(vector<vector<int>> &ans, int cur) {
    ans[0].push_back(ary[cur].idx);//프리오더
 
    if (ary[cur].left)
        travl(ans, ary[cur].left);
    if (ary[cur].right)
        travl(ans, ary[cur].right);
    ans[1].push_back(ary[cur].idx);//포스트 오더
}
 
 
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer(2);
    int n = nodeinfo.size();
 
    
 
    for (int i = 0; i < n; i++) {
        ary[i + 1] = { nodeinfo[i][1], nodeinfo[i][0], i + 1 };//x : 세로, y : 가로
    }
    sort(ary + 1, ary + n + 1, [](const node& a, const node& b)->bool {
        if (a.x != b.x) return a.x > b.x;
        return a.y < b.y;
    });
 
    int root = 1;
 
    for (int i = 2; i <= n; i++) {//트리 생성
        int prnt = root, chld = i;
        while (1) {
            if (ary[chld].y < ary[prnt].y) {//왼쪽
                if (ary[prnt].left)
                    prnt = ary[prnt].left;
                else {
                    ary[prnt].left = chld;
                    break;
                }
            }
            else {//오른쪽
                if (ary[prnt].right)
                    prnt = ary[prnt].right;
                else {
                    ary[prnt].right = chld;
                    break;
                }
            }
        }
    }
    travl(answer, 1);
        
    return answer;
}
 
int main() {
    vector < vector<int>> t = { {5,3},{11,5},{13,3},{3,5},{6,1},{1,3},{8,6},{7,2},{2,2} };
    solution(t);
 
}
 
/*
{{5,3},{11,5},{13,3},{3,5},{6,1},{1,3},{8,6},{7,2},{2,2}}
*/

정확성 테스트

테스트 1 〉	통과 (0.02ms, 3.94MB)
테스트 2 〉	통과 (0.02ms, 3.78MB)
테스트 3 〉	통과 (0.01ms, 3.97MB)
테스트 4 〉	통과 (0.01ms, 3.94MB)
테스트 5 〉	통과 (0.01ms, 3.71MB)
테스트 6 〉	통과 (1.80ms, 4.2MB)
테스트 7 〉	통과 (1.87ms, 4.14MB)
테스트 8 〉	통과 (3.48ms, 5.55MB)
테스트 9 〉	통과 (11.54ms, 9.04MB)
테스트 10 〉	통과 (1.59ms, 4.65MB)
테스트 11 〉	통과 (10.65ms, 9MB)
테스트 12 〉	통과 (11.06ms, 9.09MB)
테스트 13 〉	통과 (0.14ms, 3.96MB)
테스트 14 〉	통과 (0.84ms, 4.3MB)
테스트 15 〉	통과 (3.81ms, 5.99MB)
테스트 16 〉	통과 (7.66ms, 9.11MB)
테스트 17 〉	통과 (0.80ms, 4.27MB)
테스트 18 〉	통과 (11.05ms, 8.84MB)
테스트 19 〉	통과 (1.50ms, 4.72MB)
테스트 20 〉	통과 (3.31ms, 5.73MB)
테스트 21 〉	통과 (4.47ms, 6.89MB)
테스트 22 〉	통과 (7.48ms, 8.84MB)
테스트 23 〉	통과 (8.25ms, 9.11MB)
테스트 24 〉	통과 (0.02ms, 3.96MB)
테스트 25 〉	통과 (0.02ms, 3.94MB)
테스트 26 〉	통과 (2.96ms, 4.66MB)
테스트 27 〉	통과 (0.02ms, 3.95MB)
테스트 28 〉	통과 (0.03ms, 3.94MB)
테스트 29 〉	통과 (0.01ms, 3.93MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0