c++ 14897번 서로 다른 수와 쿼리 1 (백준)

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int n, m, nSqrt, cnt=1;

struct Query { //쿼리를 담을 구조체
	int s, e, i;
	bool operator < (Query &other) { //sort에서 구조체타입의 비교 연산을 위해 연산자 오버로딩, Mo.s 알고리즘 이용
		int a = s/nSqrt;
		int b = other.s/nSqrt;
		if(a != b) return a < b; //1. start/N의 제곱근이 더 작은것이 우선
		return e < other.e; //2. 1.의 값이 같다면 end값이 더 작은 쿼리가 우선
	}
};

int main(void) {
	map<int, int> M; //좌표압축을 위한 map
	scanf("%d", &n); 
	nSqrt = sqrt(n); //N의 제곱근
	
	int arr[n+1]; //입력받은 요소들을 담을 배열 (추후에 좌표압축된 좌표값으로 변환)
	int num[n+1]; //좌표압축된 좌표값들의 개수들을 담음
	for(int i=1; i<=n; i++) { //요소 입력 및 좌표 압축
		num[i] = 0;
		scanf("%d", &arr[i]); //요소를 입력
	
    	//좌표압축
		if(M.find(arr[i]) == M.end()) { //map에 없다면
			M[arr[i]] = cnt; //map에 새로 추가
			arr[i] = cnt++; //arr[]에 좌표압축 한 값을 대입
		} else { //map에 있다면, 기존의 좌표압축 한 값을 대입
			int tmp = M[arr[i]]; 
			arr[i] = tmp;
		}
	}
	
	scanf("%d", &m); //쿼리의 개수 입력
	int s, e, k, tmp=0, ans[m]; //ans 배열은 마지막에 쿼리들의 결과를 처음 입력받았던 순서로 처리하기 위한 배열
	vector<Query> query; //쿼리들은 sort을 이용하기 위해 벡터로 만들었습니다.
	for(int i=0; i<m; i++) { //쿼리들을 입력받습니다.
		scanf("%d %d", &s, &e);
		query.push_back({s,e,i});
	}
	sort(query.begin(), query.end()); //Mo.s 알고리즘으로 정렬합니다.
	
    //정렬된 쿼리들을 처리합니다.
	s = query[0].s;
	e = query[0].e;
	for(int i=s; i<=e; i++) { //첫번째 쿼리를 처리하고
		k = num[arr[i]]++;
		if(k == 0) tmp++;
	}
	ans[query[0].i] = tmp; //값을 저장합니다.
	
	for(int i=1; i<m; i++) { //나머지 쿼리들을 처리합니다.
		while(s < query[i].s) {
			k = --num[arr[s]];
			if(k == 0) tmp--;
			s++;
		}
		while(s > query[i].s) {
			s--;
			k = num[arr[s]]++;
			if(k == 0) tmp++;
		}
		while(e < query[i].e) {
			e++;
			k = num[arr[e]]++;
			if(k == 0) tmp++;
		}
		while(e > query[i].e) {
			k = --num[arr[e]];
			if(k == 0) tmp--;
			e--;
		}
		ans[query[i].i] = tmp;
	}
	
	for(int i=0; i<m; i++) printf("%d\n", ans[i]); //다시 쿼리의 결과들을 원래 쿼리가 입력된 순서대로 처리합니다.
}

 

풀이 : 좌표압축, Mo.s 알고리즘

 

1. 좌표의 범위가 너무 넓다보니, 좌표들을 map 자료구조를 이용하여 좌표 압축해줍니다.

 

2. 쿼리들을 입력 받고, Mo.s 알고리즘을 통한 정렬을 해줍니다. 이때, 쿼리들의 정보를 담는 과정에서 처음 쿼리들을 입력받았던 순서도 기억하고 있어야 합니다.

 

3. 정렬된 쿼리들을 순서대로 처리하고 따로 처음 쿼리들을 입력 받았던 순서대로 저장합니다.

 

4. 쿼리들의 결과를 원래 입력 받았던 순서대로 처리합니다.

 

Mo.s 알고리즘은

Q : 쿼리의 개수, N : 요소의 개수 이며

 

시간복잡도는 O ( (N+Q) * √N) 이므로 무작정 쿼리를 처리하는 경우 O(N * Q ) 보다 훨씬 빠릅니다.

 

O ( (N+Q) * √N) 인 이유

 

start의 시간 복잡도 : Q개의 쿼리 각각의 쿼리에서 start의 최대 거리는 √N 고로 O (Q * √N)

end의 시간 복잡도 : start와 달리 end는 각각의 쿼리에서 O(N)만큼 변화합니다, 여기서 중요한것은 start/√N이 같을때 end는 비내림차순 (점점 수가 증가 (같을 수도 있음)) 으로 정렬하기 때문에, 즉 하나의 버킷(start/√N이 같은 쿼리들)내에서 O(N)만큼 변화한다는 이야기이다. 즉 시간복잡도는 O (N * √N) 입니다.

 

고로 Mo.s의 시간복잡도는 O ( (N+Q) * √N) 입니다.

 

물론 쿼리들을 quick sort로 정렬하는 건 따로 봐야 합니다 (시간복잡도는 O (NlogN))

 

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

14897번: 서로 다른 수와 쿼리 1