BOJ
BOJ::12867 N차원 여행
BOJ Silver 3
BOJ::12867 N차원 여행
- Level : Silver 3
시사점
- map과 set의 사용
- Hashing의 사용
이해(30)
- Hashing으로 푸는 방법이 이해가 가지 않았다.
- 그 이유를 설명하자면,
- 전체 숫자는 n개이고, 그 중 m개만을 사용한다.
- 이때, m개 중 각각에 대해서 +1 혹은 -1을 할 수 있다.
- 이때, x+1 혹은 x-1값을 저장해서 vector에 넣어두고 lower_bound한다면 오류라고 문제가 생길거라고
생각했다.
- 예를 들어n = 10^9, m = 3, 숫자는 10, 10^5, 10^8 이고, 부호는 +++이라고 해보자.
- 따라서, 10+1, 10^5+1, 10^8+1 에 대한 배열도 할당해줘야 한다고 생각했다.
- 그렇다면 +와 -가 있으므로 총 m * 2 개의 배열을 할당해줘야 한다.
- 하지만, 실제로는 x에 해당하는 index에 값을 1 더하거나, 1 빼는 식으로 계산하면, 위와같은 고민을
하지 않아도 된다.
- 즉, 배열은 무조건 m개면 충분하다는 의미이다.
- 설명이 좀 어렵지만, 막혔던 부분을 이해하게 되었고 STL 사용한 구현법을 디버깅해보면 더 이해가 쉽다.
설계(x)
시간 복잡도
공간 복잡도
구현(60)
STL
#include <bits/stdc++.h>
using namespace std;
int n, m;
map<int,int> oneSet;
set<map<int, int> > ans;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(m);
for (int i=0; i<m; i++) {
cin >> a[i];
oneSet[a[i]] = 0;
}
string s;
cin >> s;
ans.insert(oneSet);
for (int i=0; i<m; i++) {
if (s[i] == '+') {
oneSet[a[i]] += 1;
} else {
oneSet[a[i]] -= 1;
}
ans.insert(oneSet);
}
if (ans.size() == m+1) {
cout << 1 << '\n';
} else {
cout << 0 << '\n';
}
return 0;
}
hashing
#include<bits/stdc++.h>
using namespace std;
#define MAX_M 52
int n, m;
int arr[MAX_M][MAX_M];
// m[i]에 대한 number와 부호를 의미합니다.
vector<int> numbers;
vector<char> ops;
// number를 고유 숫자로 정렬한 데이터입니다.
vector<int> vec;
int getIdx(int x){
return (int)(lower_bound(vec.begin(), vec.end(), x) - vec.begin());
}
int solve(){
for(int i = 1; i <= m; i++){
int x = getIdx(numbers[i-1]);
if(ops[i-1] == '+') arr[i][x]++;
else arr[i][x]--;
for(int j = 0; j < vec.size(); j++)
arr[i+1][j] = arr[i][j];
}
for(int i = 0; i < m; i++){
for(int j = i+1; j <= m; j++){
bool isSame = true;
for(int k = 0; k < vec.size(); k++){
if(arr[i][k] != arr[j][k]){
isSame = false;
break;
}
}
if(isSame) return 0;
}
}
return 1;
}
int main(){
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
ops = vector<char>(m);
numbers = vector<int>(m);
for(int i = 0; i < m; i++)
cin >> numbers[i];
vec.resize(numbers.size());
vec = numbers;
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
char tmp[55]={0};
cin >> tmp;
for(int i = 0; i < m; i++)
ops[i] = tmp[i];
cout << solve() << endl;
return 0;
}