[P4] 백준 15816번 퀘스트 중인 모험가 C++ 세그먼트 트리, 값/좌표 압축, 오프라인 쿼리

리뷰

 

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

퀘스트 번호의 범위가 -10억~10억이므로 값/좌표 압축을 해야하는 문제인 것은 알았다, 다만 쿼리에서 신규 퀘스트 번호가 들어옴으로 추가로 인입된 퀘스트를 어떻게 압축해 줘야할까 생각하다가 오프라인 쿼리를 사용하여 AC를 받았다.

 

 

전역 변수

• n : 지금까지 달성한 퀘스트의 개수를 저장할 변수
• m : 쿼리의 개수를 저장할 변수
• Query : 쿼리 정보를 정의할 구조체
• VI : 값을 key로, 정렬된 인덱스를 value로 저장할 해시맵
• tree : 세그먼트 트리 정보를 저장할 배열

 

함수

1. update

void update(int node, int s, int e, int idx) {
	if (s == e) tree[node]++;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx);
		else update(node * 2 + 1, mid + 1, e, idx);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

 

세그먼트 트리 업데이트를 위한 함수

 

2. query

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, L, R) + query(node * 2 + 1, mid + 1, e, L, R);
}

 

세그먼트 트리의 구간합을 구하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, 벡터 lst를 초기화 하여 n개의 이미 달성한 퀘스트의 번호를 lst에 추가해준다.
2. m값을 입력 받고, Query타입의 벡터 queries를 초기화 하고, m개의 쿼리를 입력 받아준다.
3. op가 1일경우 변수 val에 값을 추가로 입력 받고, lst에 val을 추가, 쿼리 정보를 queries에 추가해 준다.
4. op가 2일경우 변수 L, R에 값을 추가로 입력 받고, lst에 L, R을 추가, 쿼리 정보를 queries에 추가해 준다.
5. 벡터 sorted를 lst를 복사한 상태로 초기화 후 sort함수를 통해 오름차순으로 정렬해 준다.
6. sorted를 erase와 unique함수를 통해 중복이 없는 상태로 만들어준다.
7. 변수 all을 sorted의 size만큼의 값으로 저장 후 all만큼의 for문을 개행해 준다.
8. VI의 key로 sorted[i]의 값을, value를 i로 하여 값/좌표 압축을 진행해 준다.
9. n번의 for문을 개행하고, update함수를 통해 세그먼트 트리의 VI[lst[i]]번째 노드값을 증가시켜 준다.
10. queries를 순회하며 op가 1이라면 update를, 2라면 query함수를 호출해 준다.
11. query함수 수행 시 L, R에 해당하는 범위 내 구간합을 구하고 범위 - 구간합의 결과를 출력해 주면 된다.

 

트러블 슈팅

1. 처음엔 set을 활용한 풀이를 구현하였다, 하지만 구간 내 클리어한 퀘스트를 구하는 방법이 선형 탐색 외에는 존재하지 않아 O(N)의 시간이 걸렸고, 시간 초과가 발생하게 되었다.
2. 이후 세그먼트 트리를 활용한 방법을 구현하였다, 입/출력 최적화를 진행하지 않으니 마찬가지로 시간 초과가 발생하였다.
3. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);를 적용해 주니 AC를 받았다.
4. 이후 tree를 벡터가 아닌 배열로 사용하고자 포팅을 해주었으나 범위를 8000000으로 했더니 OutofBounds에러가 발생하였다.
5. op가 2일때 L, R값도 값/좌표 압축을 했으므로 최대 4000000개의 좌표 정보가 sorted벡터에 들어올 수 있었다.
6. 이를 4배를 하여 tree배열의 범위를 1600만으로 설정하니 AC를 받았다.

 

참고 사항

1. 추후에 들어올 좌표값도 알아야 하기에 오프라인 쿼리를 사용하는 방법으로 진행하였다.
2. op가 2일경우 구간을 구하는 것을 이진탐색을 사용할까 고민했다. 하지만 정렬 후 해시맵에 저장하는 것과 별반 차이가 없을 것이라 생각하여 그냥 범위에 대한하는 좌표값도 같이 압축을 진행해 주었다.
3. 다른 사람들의 풀이 결과를 보았을 때 내 풀이의 시공간 복잡도는 전혀 최적화 되지 않은 방법인 것 같다.

 

정답 코드

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

int n, m;
struct Query {
	int op, arg1, arg2;
};
unordered_map<int, int> VI;
int tree[16000000];

void update(int node, int s, int e, int idx) {
	if (s == e) tree[node]++;
	else {
		int mid = (s + e) / 2;
		if (idx <= mid) update(node * 2, s, mid, idx);
		else update(node * 2 + 1, mid + 1, e, idx);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

int query(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	return query(node * 2, s, mid, L, R) + query(node * 2 + 1, mid + 1, e, L, R);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	vector<int> lst;
	for (int i = 0; i < n; ++i) {
		int q; cin >> q;
		lst.push_back(q);
	}

	cin >> m;
	vector<Query> queries;
	for (int i = 0; i < m; ++i) {
		int op; cin >> op;
		if (op == 1) {
			int val; cin >> val;
			lst.push_back(val);
			queries.push_back({ op, val });
		}
		else {
			int L, R; cin >> L >> R;
			lst.push_back(L);
			lst.push_back(R);
			queries.push_back({ op, L, R });
		}
	}

	vector<int> sorted = lst;
	sort(sorted.begin(), sorted.end());
	sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

	int all = sorted.size();
	for (int i = 0; i < all; ++i) {
		VI[sorted[i]] = i;
	}

	for (int i = 0; i < n; ++i) {
		update(1, 0, all - 1, VI[lst[i]]);
	}

	for (const Query& q : queries) {
		int op = q.op;
		if (op == 1) update(1, 0, all - 1, VI[q.arg1]);
		else {
			int cnt = query(1, 0, all - 1, VI[q.arg1], VI[q.arg2]);
			cout << q.arg2 - q.arg1 + 1 - cnt << "\n";
		}
	}
}