BOJ 백준 23238 Best Student

 

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

 

[ 문제 요약 ]

• 배열과 쿼리가 주어지며 배열 안에 최우수 한 사람의 고유 번호가 주어집니다.
• 쿼리로 구간이 주어지면 그 안에서 최우수 한 사람의 고유 번호가 가장 많이 등장한 사람의 고유 번호를 출력합니다. 횟수가 같다면 고유 번호가 더 큰 사람의 번호를 출력합니다.

 

[ 테스트 케이스 설명 ]

5 3		// 일자(1<=100,000), 쿼리 수(1<=100,000)
2 1 2 1 1	// 1일부터N일 까지의 최우수 학생 ID 번호를 나타내는 N개의 양의 정수 (1<=10^9)
1 2		// s일 부터 e일 까지
1 4
1 5
//출력 : S,E 동안 가장 자주 최우수 학생으로 선발된 학생의 ID 출력, 여러명이면 그 중ID번호가 큰것 출력
2
2
1

 

 

[ 알고리즘 분류 ]

• 오프라인 쿼리
• 제곱근 분할법
• mo’s 알고리즘

 

[ 문제 해설 ]

 

이 문제에서 주어지는 학생들의 ID가 최대 10억이므로 카운팅 배열로 처리하기 위해서는 값 압축을 해야 합니다. 압축할 때 편의상 map을 사용하는데 그러면 시간 초과를 받게 되어 이분 탐색으로 압축해야 합니다. 이분 탐색이 훨씬 빠릅니다.

 

또한 이 문제 시간제한이 1.2초로, 자바로 풀 때 추가로 주는 시간이 없어서, 주어지는 값을 입력받을 때 BufferedReader로 사용하면 시간 초과라 빠른 입력으로 입력을 받아야 겨우 시간 안에 통과할 수 있습니다. 아래는 빠른 입력을 할 수 있는 Reader 클래스와, 또는 int형 만 빠르게 입력을 받을 수 있는 read 함수 두 개를 올려드립니다.

 

// 빠른 입력이 가능한 Reader 클래스

class Reader {
    final int SIZE = 1 << 13;
    byte[] buffer = new byte[SIZE];
    int index, size;

    String nextString() throws Exception {
        StringBuilder sb = new StringBuilder();
        byte c;
        while ((c = read()) < 32) { if (size < 0) return "endLine"; }
        do sb.appendCodePoint(c);
        while ((c = read()) >= 32); // SPACE 분리라면 >로, 줄당 분리라면 >=로
        return sb.toString();
    }

    char nextChar() throws Exception {
        byte c;
        while ((c = read()) < 32); // SPACE 분리라면 <=로, SPACE 무시라면 <로
        return (char)c;
    }
    
    int nextInt() throws Exception {
        int n = 0;
        byte c;
        boolean isMinus = false;
        while ((c = read()) <= 32) { if (size < 0) return -1; }
        if (c == 45) { c = read(); isMinus = true; }
        do n = (n << 3) + (n << 1) + (c & 15);
        while (isNumber(c = read()));
        return isMinus ? ~n + 1 : n;
    }

    long nextLong() throws Exception {
        long n = 0;
        byte c;
        boolean isMinus = false;
        while ((c = read()) <= 32);
        if (c == 45) { c = read(); isMinus = true; }
        do n = (n << 3) + (n << 1) + (c & 15);
        while (isNumber(c = read()));
        return isMinus ? ~n + 1 : n;
    }

    double nextDouble() throws Exception {
        double n = 0, div = 1;
        byte c;
        boolean isMinus = false;
        while ((c = read()) <= 32) { if (size < 0) return -12345; }
        if (c == 45) { c = read(); isMinus = true; }
        else if (c == 46) { c = read(); }
        do n = (n * 10) + (c & 15);
        while (isNumber(c = read()));
        if (c == 46) { while (isNumber(c = read())){ n += (c - 48) / (div *= 10); }}
        return isMinus ? -n : n;
    }

    boolean isNumber(byte c) {
        return 47 < c && c < 58;
    }

    boolean isAlphabet(byte c){
        return (64 < c && c < 91) || (96 < c && c < 123);
    }

    byte read() throws Exception {
        if (index == size) {
            size = System.in.read(buffer, index = 0, SIZE);
            if (size < 0) buffer[0] = -1;
        }
        return buffer[index++];
    }
}

// int 범위 내에서 빠른 입력을 할 수 있는 함수
    static int read() throws Exception {
        int c, n = System.in.read() & 15;
        boolean m = n == 13;
        if (m)n = System.in.read() & 15;
        while ((c = System.in.read()) >= 48) {
        n = (n << 3) + (n << 1) + (c & 15);}
        return m ? ~n + 1 : n;
    }

 

 

학생의 ID를 압축한 후, 그 압축된 ID 값을 기준으로 제곱근 분할을 진행합니다.

 

각 학생들의 ID마다 몇 번 등장했는지 확인할 수 있는 카운팅 배열 cnt를 선언,

 

각 학생들의 ID를 제곱근 분할하여, 그 구간 안에 등장한 가장 큰 학생의 등장 횟수를 저장할 배열 fac 선언, 그리고 fac의 값이 감소할 때, 감소할지 말지를 추적할 배열 facFreq를 선언합니다.

 

fac 배열은 제일 큰 값만 저장하면 되므로 값의 증가에 추적이 필요 없으나 감소는 필요합니다.

 

facFreq 배열은 제곱근 구간 안에서 등장 횟수의 등장 횟수를 추적하는 배열입니다. 이 배열이 있어야, 같은 등장 횟수가 여러 개일 경우, 값을 제대로 추적할 수 있습니다.

 

최종적으로 값을 찾을 때는 제곱근 배열 fac에서 최대값을 찾아서 그 구간 안에 cnt 값이 가장 큰 노드 번호를 출력합니다. 이때 노드 번호는 압축한 노드 번호이므로 복원 후 저장해야 합니다.

 

이 문제는 제곱근 분할을 어디에 적용하고, 값의 변동을 어떻게 추적할지를 이해해야 합니다.

 

[ 정답 코드 ]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Main{
	
	static int N, Q;
	static int idx;// 좌표 압축 후 가장 큰 학생의 번호
	static int sqrt;// 학생의 번호를 구간으로 나눌 제곱근 값
	static int ans[];// 최종 결과를 담을 배열
	static int arr[];// 처음 입력되는 학생의 번호
	static int brr[];// 좌표 압축에 사용할 배열
	static int cnt[];// idx : 학생의 번호, value : 그 학생의 등장 횟수
	static int fac[];// idx : 학생번호의 구간, value : 해당 구간의 등장한 최대 횟수
	static int facFreq[][];// 각 학생의 구간마다 등장 횟수의 등장횟수를 담는 배열, value : 등장 횟수
	static List<Query> query;
	
	public static void main(String[] args)throws Exception{
		Reader in = new Reader();
		N = in.nextInt();
		Q = in.nextInt();
		sqrt = (int)Math.sqrt(N);
		ans = new int[Q + 1];
		arr = new int[N + 1];
		brr = new int[N + 1];
		cnt = new int[100_001];
		fac = new int[N / sqrt + 1];
		facFreq = new int[N / sqrt + 1][N + 1];
		query = new ArrayList<>();
		// 좌표 압축을 위해 brr배열에 같은 값을 담음
		for(int i=1; i<=N; i++)
			arr[i] = brr[i] = in.nextInt();
		
		Arrays.sort(brr);// 좌표 압축을 위한 정렬
		
		// 좌표 압축 및 압축 값의 가장 큰 값을 idx에 저장
		for(int i=1; i<=N; i++)
		{
			arr[i] = binarySearch(arr[i]);
			if(idx < arr[i])
				idx = arr[i];
		}
		// 쿼리를 입력 받음
		for(int i=1; i<=Q; i++)
		{
			int s = in.nextInt();
			int e = in.nextInt();
			query.add(new Query(s, e, i, s / sqrt));
		}
		// mo's 정렬 
		Collections.sort(query);
		
		int s = 1;
		int e = 0;
		
		for(Query q : query)
		{
			while(e < q.e) plus(arr[++e]);
			while(q.s < s) plus(arr[--s]);
			while(q.e < e) minus(arr[e--]);
			while(s < q.s) minus(arr[s++]);
			// ans에 값을 담을 때 값 압축 전 값으로 저장
			ans[q.idx] = brr[ find() ]; 
		}
		
		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 nodeNum) {
		// 해당 노드 번호의 구간을 구함
		int facIdx = nodeNum / sqrt;
		// 해당 구간의 등장 횟수(cnt[nodeNum])이 0이 되었고,
		// 그 등장 횟수(cnt[nodeNum])이 해당 구간(fac[facIdx])의 최댓 값이였을 경우
		// 그 최댓 값(fac[facIDx])을 -1 감소 시킴
		if(--facFreq[facIdx][cnt[nodeNum]] == 0 && fac[facIdx] == cnt[nodeNum])
			--fac[facIdx];
		// 해당 학생 등장 횟수 하나 감소
		--cnt[nodeNum];
	}
	static void plus(int nodeNum) {
		int facIdx = nodeNum / sqrt;
		// 해당 학생 등장 횟수 하나 추가
		++cnt[nodeNum];
		// 해당 학생이 있는 구간의 최댓 값 갱신
		fac[facIdx] = Math.max(fac[facIdx], cnt[nodeNum]);
		// 해당 학생이 있는 구간의 해당 등장횟수(cnt[nodeNum]) 값 증가
		++facFreq[facIdx][cnt[nodeNum]];
	}
	static int find() {
		int max = 0;
		// 구간에서 가장 큰 값을 모두 순회하여 찾아냄
		for(int i=0; i<fac.length; i++)
			max = Math.max(fac[i], max);
		
		// 구간에 대해 역으로 순회하며, max와 같은 첫번 째 값만 연산대상
		for(int i=fac.length - 1; i>=0; i--)
		{
			if(fac[i] != max)
				continue;
			// 해당 구간의 s와 e를 구해서 그중 max와 같은 최대 등장 횟수를
			// 갖는 학생 아이디를 반환함
			int s = i * sqrt;
			int e = Math.min(s + sqrt, idx);
			while(e >= s)
			{
				if(cnt[e] == max)
					return e;
				--e;
			}
		}
		return 0;
	}
	static int binarySearch(int target) {
		int s = 1;
		int e = N;
		int res = 0;
		
		while(s <= e)
		{
			int mid = (s + e) >> 1;

			if(brr[mid] < target)
				s = mid + 1;
			else
			{
				res = mid;
				e = mid - 1;
			}
		}
		
		return res;
	}
	static class Query implements Comparable<Query>{
		int s, e, idx, fac;
		Query(int s, int e, int idx, int fac){
			this.s=s;
			this.e=e;
			this.idx=idx;
			this.fac=fac;
		}
		@Override
		public int compareTo(Query o) {
			if(fac != o.fac)
				return fac - o.fac;
			
			if((fac&1) == 0)
				return e - o.e;
			
			return o.e - e;
		}
	}
}

class Reader {
    final int SIZE = 1 << 13;
    byte[] buffer = new byte[SIZE];
    int index, size;

    int nextInt() throws Exception {
        int n = 0;
        byte c;
        boolean isMinus = false;
        while ((c = read()) <= 32) { if (size < 0) return -1; }
        if (c == 45) { c = read(); isMinus = true; }
        do n = (n << 3) + (n << 1) + (c & 15);
        while (isNumber(c = read()));
        return isMinus ? ~n + 1 : n;
    }

    boolean isNumber(byte c) {
        return 47 < c && c < 58;
    }

    byte read() throws Exception {
        if (index == size) {
            size = System.in.read(buffer, index = 0, SIZE);
            if (size < 0) buffer[0] = -1;
        }
        return buffer[index++];
    }
}