BOJ 백준 2912 백설공주와 난쟁이

 

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

[ 문제 요약 ]

• 배열과 배열의 초깃값이 주어지고, 범위가 주어졌을 때, 그 범위 안의 숫자 종류 중 가장 많은 숫자의 수가 범위 안 모든 숫자 개수의 과반을 초과할 때 yes와 함께 그 숫자 출력, 과반 이하일 때는 no를 출력합니다.

 

[ 테스트 케이스 설명 ]

10 3			// 난쟁이 수(3<=300,000), 모자 색상 수(1<=10,000)
1 2 1 2 1 2 3 2 3 3	// 모자의 색상이 줄을 서 있는 순서대로 주어짐
8			// 질의 수 (1<=10,000)
1 2			// 범위
1 3
1 4
1 5
2 5
2 6
6 9
7 10
// 답
no	// 절반이 넘는 모자의 색상이 같지 않으면 no출력
yes 1	// 절반이 넘는 모자의 색상이 같으면 해당 모자 수 출력
no
yes 1
no
yes 2
no
yes 3

 

[ 알고리즘 분류 ]

• 자료 구조, 오프라인 쿼리, Mo’s
• 무작위화

 

[ 문제 해설 ]

배열의 값을 변경하는 것이 없으므로, mo’s 알고리즘을 이용해 빠르게 답을 구할 수 있습니다.

 

Mo’s 알고리즘은 모든 쿼리를 오프라인으로 모아서, 왼쪽 포인터 L과 오른쪽 포인터 R을 한 칸씩만 움직이도록 쿼리 순서를 정렬해 O((N + Q) √ N) 시간에 해결하는 테크닉입니다.

 

Mo's 알고리즘 정렬 방법은 아주 간단한데,

 

[ i, j ] 구간이 주어지면, i / sqrt(N) 기준으로 오름차순 정렬합니다. 만약 값이 같은 경우 j 기준으로 오름차순 정렬합니다. 이렇게 쿼리들을 정렬해놓고 순서대로 답을 구하면 최소 이동으로 답을 구하게되므로 빠르게 처리 가능합니다.

 

Mo’s 알고리즘은 정렬할 때만 사용하고 실제 답을 구할 때는 투포인터와 같이 left, right 인덱스를 적절히 움직이며 답을 구합니다.

 

저는 maxColor라는 변수를 두어 답을 바로 구할 수 있게 하고, 최종 결과 대 입전에 컬러 확인을 못한 부분이 없는지 추가 확인하여 놓치는 것 없도록 했습니다.

 

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

 

[ 정답 코드 ]

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N		= Integer.parseInt(st.nextToken());// 난쟁이 수(3<=300,000)
		int C		= Integer.parseInt(st.nextToken());// 모자 색상 수(1<=10,000)
		int arr[]	= new int[N + 1];
		int color[] = new int[C + 1];
		sqrt		= (int)Math.sqrt(N);
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		ArrayList<Query> query = new ArrayList<>();
		int Q = Integer.parseInt(br.readLine());
		int ans[] = new int[Q + 1];
		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;
		
		for(Query q : query)
		{
			int limit = (q.right - q.left + 1) / 2 + 1;
			int maxColor = 0;
			
			while(q.right < idxR)
				--color[arr[idxR--]];
			
			while(idxL < q.left)
				--color[arr[idxL++]];
			
			while(idxR < q.right)
				if(++color[arr[++idxR]] >= limit)
					maxColor = arr[idxR];
			
			while(q.left < idxL)
				if(++color[arr[--idxL]] >= limit)
					maxColor = arr[idxL];
			// 컬러를 못 찾은 경우, 해당 범위안을 전부 확인하여 답을 구함
			if(maxColor == 0)
			{
				for(int c=1; c<=C; c++)
				{
					if(color[c] >= limit)
					{
						maxColor = c;
						break;
					}
				}
			}
			
			ans[q.idx] = maxColor;
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=Q; i++)
		{
			if(ans[i] == 0)
				sb.append("no").append('\n');
			else
				sb.append("yes ").append(ans[i]).append('\n');
		}
		
		System.out.print(sb);
	}
}