백준 12867번: N차원 여행 (C++)

https://www.acmicpc.net/problem/12867

12867번: N차원 여행

---

Solved By: Coordinate Compression

 

차원의 크기 N은 [1, 1,000,000,000]으로 너무 큽니다. 크기가 1,000,000,000인 배열을 선언하기는 부담스러우니 차원(값) 압축을 시킵시다.

 

하지만, 문제는 중복된 좌표를 어떻게 알고 처리할지가 문제였습니다. string으로 처리하자니 한 차원의 자리가 두 자리가 넘어가면 난감했습니다.

 

그때 발견한 테크닉은 신기했습니다. set에서 vector<int>까지 담을 수 있는 것이었습니다.

이 점을 활용하여 좌표가 이동할 때마다 해당 배열이 있는지 set을 통해 확인하여 문제를 풀 수 있었습니다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

set<vector<int>> st; // new tech
int n, m;
vector<int> v;
vector<int> temp;

int main(){
    cin >> n >> m;
    for(int i = 0, value; i < m; i++){
        cin >> value;
        v.push_back(value); temp.push_back(value);
    }
    
    // Coordinate Compression
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    
    vector<int> coor(temp.size());
    st.insert(coor);
    
    bool flag = 1;
    string s; cin >> s;
    for(int i = 0; i < m; i++){
        int idx = lower_bound(temp.begin(), temp.end(), v[i]) - temp.begin();
        if(s[i] == '+'){
            coor[idx] += 1;
        }
        else{
            coor[idx] -= 1;
        }
        
        if(st.count(coor)){
            flag = 0; break;
        }
        else{
            st.insert(coor);
        }
    }
    
    if(flag) cout << 1;
    else cout << 0;
    
    return 0;
}