[프로그래머스 Level 3] 길 찾기 게임 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

처음 든 생각은 'x에 대해서 정렬한 다음 다음 노드에 대해서만 조건을 따지면 되겠다'이었다. 

그리고 나서 현재 노드와 다음 노드에 대해서 y값을 비교한다음 다음 노드가 현재 노드보다 y값이 작으면 현재 노드에 오른쪽 자식이 되도록 설정하고, 만약 크면 다음 노드의 왼쪽 자식에 현재 노드를 집어 넣도록 하려했다. 이 때 현재 노드를 넣을 때 현재 노드가 가리키는 최상단의 부모를 넣어줘야 한다.

주의할 점으로 다음노드가 더 클 때는 조건을 나눠줘야 하는데 부모가 다음 노드보다 y의 값이 클 경우와 작을 경우이다. 이 점만 주의해서 코딩을 하면 쉽게 풀린다

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <memory.h>
using namespace std;

int parent[100001];
int l[100001];
int r[100001];
map<int, pair<int,int>> m;
vector<int> a;
vector<int> b;

bool compare(pair<int, pair<int,int>> a, pair<int, pair<int,int>> b){
    return a.second.first<b.second.first;
}

void preOrder(int node){
    if(node==0)
        return;
    a.push_back(node);
    preOrder(l[node]);
    preOrder(r[node]);
}

void postOrder(int node){
    if(node==0)
        return;
    postOrder(l[node]);
    postOrder(r[node]);
    b.push_back(node);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    memset(parent, -1, sizeof(parent));
    //먼저 순서에 따른 순서값 저장해주면서 이후 x좌표 순으로 정렬해준다.
    vector<pair<int,pair<int,int>>> v;
    int topNode=-1;
    int topY=-1;
    for(int i = 0 ; i < nodeinfo.size(); i++){
        v.push_back({i+1,{nodeinfo[i][0],nodeinfo[i][1]}});
        m[i+1]={nodeinfo[i][0],nodeinfo[i][1]};
        if(topY<nodeinfo[i][1]){
            topNode=i+1;
            topY=nodeinfo[i][1];
        }
    }
    sort(v.begin(), v.end(), compare);
    for(int i = 1 ; i <v.size(); i++){
//        cout<<v[i].first<<" ";
        if(v[i-1].second.second>v[i].second.second){
            r[v[i-1].first]=v[i].first;
            parent[v[i].first]=v[i-1].first;
        }else{
            int tmp = v[i-1].first;
            int tmp2=0;
            while(parent[tmp]!=-1){
                tmp2=tmp;
                tmp = parent[tmp];
                if(m[tmp].second>v[i].second.second){
                    break;
                }
            }
            if(m[tmp].second>v[i].second.second){
                l[v[i].first]=tmp2;
                r[tmp]=v[i].first;
                parent[v[i].first]=tmp;
            }else{
                l[v[i].first]=tmp;
            }
        }
    }
    
//    for(int i = 1; i<=nodeinfo.size(); i++){
//        cout<<l[i]<<" "<<r[i]<<endl;
//    }
    preOrder(topNode);
    postOrder(topNode);
    answer.push_back(a);
    answer.push_back(b);
    return answer;
}