BOJ 백준 13028 민호의 소원

 

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

 

[ 문제 요약 ]

• 배열과 그 원소가 주어지고, 구간이 주어졌을 때, 해당 구간 안에서 세 번 이상 등장하는 수의 종류의 개수를 출력합니다.

 

[ 테스트 케이스 설명 ]

9 7			// 배열길이(1<=100,000), 질의수(1<=100,000)
3 2 3 1 3 1 2 1 1	// 원소 수 1<=100,000
3 7
1 7
8 9
3 7
1 3
2 4
1 8
//답
0
1
0
0
0
0
2

 

 

[ 알고리즘 분류 ]

• 오프라인 쿼리
• 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)”를 지원하지 못한다는 점으로, 그런 경우에는 세그먼트 트리나 펜윅 트리 같은 자료구조를 써야 합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader	br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N		= Integer.parseInt(st.nextToken());// 배열길이(1<=100,000)
		int Q		= Integer.parseInt(st.nextToken());// 질의수(1<=100,000)
		int arr[]	= new int[N + 1];
		int ans[]	= new int[Q + 1];
		int cnt[]	= new int[100_001];
		int sqrt	= (int)Math.sqrt(N);
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			arr[i] = Integer.parseInt(st.nextToken());// 원소 수 1<=100,000
		
		ArrayList<Query> 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);
		
		int L = 1;
		int R = 0;
		int count = 0;
		for(Query q : query)
		{
			while(R < q.right)
				if(++cnt[arr[++R]] == 3)
					++count;

			while(q.right < R)
				if(--cnt[arr[R--]] == 2)
					--count;
			
			while(L < q.left)
				if(--cnt[arr[L++]] == 2)
					--count;

			while(q.left < L)
				if(++cnt[arr[--L]] == 3)
					++count;
			
			ans[q.idx] = count;
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=Q; i++)
			sb.append(ans[i]).append('\n');
		
		System.out.print(sb);
	}
	static class Query implements Comparable<Query>{
		int left, right, idx, fac;
		Query(int l, int r, int i, int f){
			this.left = l;
			this.right= r;
			this.idx = i;
			this.fac = f;
		}
		@Override
		public int compareTo(Query o) {
			return fac == o.fac ? right - o.right : fac - o.fac;
		}
	}
}