BOJ 백준 13548 수열과 쿼리 6

 

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

[ 문제 요약 ]

• 배열과 그 원소가 주어지고 특정 구간들이 주어집니다.
• 구간들 사이에 가장 많이 등장하는 수가 몇 번 등장하는지 출력합니다.

 

[ 테스트 케이스 설명 ]

5		// 수열 크기 1<=100,000
1 2 1 3 3	// 1<=100,000
3		// 쿼리수 1<=100,000
1 3
2 3
1 5
// 답
2
1
2

 

[ 알고리즘 분류 ]

• 오프라인 쿼리, Mo’s 알고리즘

 

[ 문제 해설 ]

 

위 문제는 오프라인 쿼리로 처리하면서 Mo’s 알고리즘을 이용해 쿼리를 정렬하고, 투포인터로 풀듯이 문제를 풀면 됩니다.

 

여기서 중요한 것은, 특정 수의 빈도를 체크하는 변수 cnt를 둔다면, 이 cnt가 몇 개가 있는지 추적하는 freq 배열을 따로 두어야 합니다. 빈도수의 빈도를 체크해야 max 값을 제대로 추적할 수 있습니다.

 

아래 코드는 오프라인 쿼리로 Mo’s를 활용한 정렬과, 투포인터 알고리즘을 사용한 정답 코드입니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
class Main{
	
	static int sqrt;
	
	static class Query implements Comparable<Query>{
		int left, right, idx;
		Query(int l, int r, int i){
			left = l;
			right=r;
			idx = i;
		}
		@Override
		public int compareTo(Query o) {
			int l = left / sqrt;
			int r = o.left / sqrt;
			return l == r ? right - o.right : l - r;
		}
	}
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N		= Integer.parseInt(br.readLine());// 수열 크기 1<=100,000
		int arr[]	= new int[N + 1];
		int cnt[]	= new int[100_001];
		int freq[]	= new int[100_001];	// 빈도수가 i인 숫자의 개수
		sqrt		= (int)Math.sqrt(N);
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			arr[i] = Integer.parseInt(st.nextToken());// 1<=100,000
		
		int Q = Integer.parseInt(br.readLine());// 쿼리수 1<=100,000
		int ans[] = new int[Q + 1];
		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));
		}
		
		Collections.sort(query);
		
		int idxL = 1;
		int idxR = 0;
		int max = 0;
		for(Query q : query)
		{
			while(idxR < q.right)
			{
				++idxR;
				--freq[cnt[arr[idxR]]];
				++freq[++cnt[arr[idxR]]];
				max = Math.max(max, cnt[arr[idxR]]);
			}
			
			while(q.right < idxR)
			{
				if(--freq[cnt[arr[idxR]]] == 0 && max == cnt[arr[idxR]])
					--max;

				++freq[--cnt[arr[idxR]]];
				--idxR;
			}
			
			while(idxL < q.left)
			{
				if(--freq[cnt[arr[idxL]]] == 0 && max == cnt[arr[idxL]])
					--max;

				++freq[--cnt[arr[idxL]]];
				++idxL;
			}
            
			while(q.left < idxL)
			{
				--idxL;
				--freq[cnt[arr[idxL]]];
				++freq[++cnt[arr[idxL]]];
				max = Math.max(max, cnt[arr[idxL]]);
			}

            
			ans[q.idx]= max;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=Q; i++)
			sb.append(ans[i]).append('\n');
		
		System.out.print(sb);
	}
}