BOJ 백준 14413 Poklon

 

문제 : https://www.acmicpc.net/problem/14413

 

[ 문제 요약 ]

• 배열과 원소가 주어집니다. 원소 값의 범위는 1~10억입니다.
• 그리고 배열의 구간이 주어질 때, 해당 구간에서 딱 2번만 등장하는 숫자의 수를 카운팅 해서 출력합니다.

 

[ 테스트 케이스 설명 ]

5 2		// 배열 수, 질의수(1<=500,000)
1 1 1 1 1	// 원소 값 1<=1,000,000,000
2 4
2 3
답
0
1

 

 

[ 알고리즘 분류 ]

• 값 / 좌표 압축
• Mo’s 알고리즘
• 오프라인 쿼리

 

[ 문제 해설 ]

 

update가 없는 쿼리 문제로 오프라인 쿼리로 처리합니다.

 

쿼리들을 처리할 때 결과적으로 하나하나 다 구해봐야 하므로, 기존에 구한 값을 활용하면서 두 포인터의 이동을 최소한으로 할 수 있도록 Mo’s 알고리즘으로 정렬 후 풀면 됩니다.

 

Mo’s 알고리즘은 배열을 sqrt(N) 구간으로 나눠 투 포인터의 이동을 최소화하는 알고리즘입니다.

 

범위의 왼쪽을 L, 오른쪽을 R이라 할 때, L / sqrt(N)으로 먼저 정렬하고, 같으면 R을 기준으로 오름차순 정렬합니다.

 

이렇게 하면 연속한 두 쿼리 사이에서 L 과 R 이 한 번에 멀리 점프하는 일이 거의 사라져, 전체 이동 횟수가 O((N+Q)√ N)에 그치게 됩니다.

 

프로그램은 정렬된 쿼리를 순서대로 따라가며 현재 구간 [L, R]에서 한 칸씩만 포인터를 늘리거나 줄이고, 움직일 때마다 상수 시간으로 빈도 배열을 갱신해 최빈도·합계·고유값 수 등 원하는 통계를 유지합니다.

 

결국 정렬에 O(Q log Q) 또는 O(Q) (블록 정렬이므로 보통 O(Q log Q) 이하), 쿼리 처리에 O((N+Q)√N) 이 걸려 총 시간 복잡도는 O((N+Q)√N), 메모리는 카운트 배열과 쿼리 리스트를 합해 O(N+Q)입니다.

 

단점은 “배열 값이 바뀌는 실시간 업데이트(online query)”를 지원하지 못한다는 점으로, 그런 경우에는 세그먼트 트리나 펜윅 트리 같은 자료구조를 써야 합니다.

 

그리고 이 문제에서 입력되는 원소가 10억이므로 숫자를 추적하기 위해서는 값 압축이 필요합니다. 이를 위해 TreeSet을 사용했습니다.

 

디테일은 코드를 통해 확인 가능합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;
class Main{
	
	static int idx;	// 값 압축시 사용하는 flag
	static int sqrt;
	static int twoCnt;
	static int N, Q;
	static int [] arr, ans, count;
	static ArrayList<Query> query;
	
	public static void main(String[] args)throws Exception{
		init();		// 해당 함수에서 배열을 입력받고, 값 압축을 진행하고, 쿼리들도 입력받아 Mo's알고리즘으로 정렬
		solve();	// 해당 함수에서 정렬된 쿼리들을 투포인터를 이용해 결과를 저장
		print();	// 해당 함수에서 저장된 결과를 출력
	}
	
	static void init()throws Exception{
		BufferedReader	br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N		= Integer.parseInt(st.nextToken());// 배열 수(1<=500,000)
		Q		= Integer.parseInt(st.nextToken());// 질의 수(1<=500,000)
		arr		= new int[N + 1];
		ans		= new int[Q + 1];
		sqrt	= (int)Math.sqrt(N);
		
		// 값 입력 및 좌표 압축 진행
		TreeSet<Integer> set = new TreeSet<>();
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
		{
			arr[i] = Integer.parseInt(st.nextToken());
			set.add(arr[i]);
		}
		HashMap<Integer,Integer> map = new HashMap<>();
		for(int s : set)
			map.put(s, ++idx);
		
		for(int i=1; i<=N; i++)
			arr[i] = map.get(arr[i]);
		
		// 쿼리를 입력 받은 후 Mo's알고리즘으로 정렬
		query = new ArrayList<>();
		for(int i=1; i<=Q; i++)
		{
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			query.add(new Query(l, r, i, l / sqrt));
		}
		
		Collections.sort(query);
	}
	static void solve() {
		// 2개인 것의 개수를 구함
		count = new int[idx + 1];
		twoCnt = 0;
		int L = 1;
		int R = 0;
		for(Query q : query)
		{
			while(R < q.right)	plus(arr[++R]);
			while(q.right < R)	minus(arr[R--]);
			while(L < q.left)	minus(arr[L++]);
			while(q.left < L)	plus(arr[--L]);
			
			ans[q.idx] = twoCnt; 
		}
	}
	static void print() {
		// 결과 출력
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=Q; i++)
			sb.append(ans[i]).append('\n');
		
		System.out.print(sb);
	}
	
	static void minus(int num) {
		if(count[num] == 3)
			++twoCnt;
		else if(count[num] == 2)
			--twoCnt;
		
		--count[num];
	}
	static void plus(int num) {
		if(count[num] == 1)
			++twoCnt;
		else if(count[num] == 2)
			--twoCnt;
		
		++count[num];
	}
	static class Query implements Comparable<Query>{
		int left, right, idx, fac;
		Query(int l, int r, int i, int f){
			left = l;
			right = r;
			idx = i;
			fac = f;
		}
		
		@Override
		public int compareTo(Query o) {
			return fac == o.fac ? right - o.right : fac - o.fac;
		}
	}
}