길 찾기 게임

• 문제

programmers.co.kr/learn/courses/30/lessons/42892

• 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

class Node{
    public:
        int id;
        Node *left;
        Node *right;
        Node(){
            left = NULL;
            right = NULL;
        }
        
};

map<int, vector<pair<int,int>>> y_node;

vector<vector<pair<int,int>>> points;

int find_dir(int y_idx, int a, int b){

    int start = 0;
    int end = points[y_idx].size()-1;
    int mid;
    while(start <= end){
        mid = (start+end)/2;
        int tmp_val = points[y_idx][mid].first;
        if(a < tmp_val && tmp_val < b)
            break;
        else if(tmp_val < a)
            start = mid + 1;
        else if(b < tmp_val)
            end = mid - 1;
    }
    return mid;
    
}




Node* dfs(int y_idx, int x_idx, int low, int high){
    Node *cur_node = new Node();
    cur_node->id = points[y_idx][x_idx].second;
    int x_val = points[y_idx][x_idx].first;
    if(y_idx+1 < points.size()){
        
        int lb = find_dir(y_idx+1, low, x_val);
        int tmp_val = points[y_idx+1][lb].first;
        if(low < tmp_val && tmp_val < x_val){
            // cout << "id " << cur_node->id << " left : " << points[y_idx+1][lb].second << '\n';
            cur_node->left = dfs(y_idx+1, lb, low, x_val);
        }
        
        int ub = find_dir(y_idx+1, x_val, high);
        tmp_val = points[y_idx+1][ub].first;
        if(x_val < tmp_val && tmp_val <= high){
            // cout << "id " << cur_node->id << " right : " << points[y_idx+1][ub].second << '\n';
            cur_node->right = dfs(y_idx+1, ub, x_val, high);
        }
    }
    
    return cur_node;
}

void pre_travel(vector<int> &pre_vec, Node* cur_node){
    pre_vec.push_back(cur_node->id);
    if(cur_node->left)
        pre_travel(pre_vec, cur_node->left);
    if(cur_node->right)
        pre_travel(pre_vec, cur_node->right);
}

void post_travel(vector<int> &post_vec, Node* cur_node){
    if(cur_node->left)
        post_travel(post_vec, cur_node->left);
    if(cur_node->right)
        post_travel(post_vec, cur_node->right);
    post_vec.push_back(cur_node->id);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    
    for(int i=0; i<nodeinfo.size(); i++){
        int x = nodeinfo[i][0];
        int y = nodeinfo[i][1];
        y_node[y].push_back({x,i+1});
    }
    stack<int> s;
    for(auto iter=y_node.begin(); iter != y_node.end(); iter++)
        s.push(iter->first);
    
    while(!s.empty()){
        int cur_idx = s.top();
        s.pop();
        points.push_back(y_node[cur_idx]);
    }
    
    int min_val = 2e9;
    int max_val = -2e9;
    
    for(int i=0; i<points.size(); i++){
        sort(points[i].begin(), points[i].end());
        min_val = min(min_val, points[i][0].first);
        max_val = max(max_val, points[i][points[i].size()-1].first);
    }

    
    
    Node* root = dfs(0,0,min_val-1,max_val+1);
    
    vector<int> pre_vec;
    vector<int> post_vec;
    pre_travel(pre_vec, root);
    post_travel(post_vec, root);
    answer.push_back(pre_vec);
    answer.push_back(post_vec);
    return answer;
}

• 피드백
  • 푸는 아이디어에 도달하는데 굉장히 오래 걸린 문제 .... 2시간 반 만에 풀었다고 생각한다.
  • 처음에 그 큰 좌표에서 어떻게 좌표들을 서칭해야하나 고민만 오지게 한듯 .. x,y 최대 크기가 100000 이고 좌표들의 갯수 또한 100000이기 때문에 좌표들을 모두 서칭할 수 없었다.
  • 결론은 이분 탐색을 이용하는 것이었다. 각 좌표들은 자신들만이 존재할 수 있는 영역이 존재하기 때문에 그냥 이분탐색 하면 log 100000 = 16으로 O(NlogN) = 100000*16 = 1600000 으로 풀 수 있는 시간복잡도가 된다.
  • 큰 수가 등장하고 뭔가 찾아야 한다면 이분탐색을 잊지말자, 이것을 떠올리는데 오래 걸렸다.