백준 13548 수열과 쿼리 6 JAVA 풀이 (Mo's Algorithm, 오프라인 쿼리)

🔗 문제 링크

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

---

📌 문제 개요

수열이 주어지고 여러 개의 구간 쿼리가 주어진다.
각 쿼리마다 구간 [L, R]에서 가장 많이 등장한 숫자의 등장 횟수(최빈값의 빈도)를 구해야 한다.

---

📌 접근 방법

이 문제는 단순히 각 구간을 매번 계산하면 시간 초과가 발생한다.

• 각 쿼리마다 O(N) → 전체 O(N * M) → 불가능
• 따라서 구간을 이동하면서 계산하는 Mo's Algorithm을 사용한다

Mo 알고리즘은 쿼리를 정렬한 뒤,
현재 구간을 유지하면서 조금씩 이동하며 계산하는 방식이다.

---

📌 핵심 아이디어

1. count 배열

count[x] = 값 x가 현재 구간에서 몇 번 등장했는지

 

 

 

2. freq 배열

freq[k] = k번 등장하는 값이 몇 개 있는지

 

핵심 포인트 : 최빈값을 빠르게 유지하기 위해 필요

 

 

3. maxFreq 유지

현재 구간에서 가장 많이 등장한 횟수

 

 

 

4. add / remove

add(x)

• count[x] 증가
• freq 갱신
• maxFreq 증가 가능

remove(x)

• count[x] 감소
• freq 갱신
• maxFreq 감소 필요 여부 체크

---

📌 처리 흐름

쿼리 입력 → Mo 정렬 (L 블록 기준) → curL, curR 초기화 → 각 쿼리 처리 → 결과 저장 → 출력

while(curL > L) add(--curL)
while(curR < R) add(++curR)
while(curL < L) remove(curL++)
while(curR > R) remove(curR--)​

---

📌 전체 코드

package no_13548;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class No13548 {

    static class Query {
        int l, r, idx;

        public Query(int l, int r, int idx) {
            this.l = l;
            this.r = r;
            this.idx = idx;
        }
    }

    static int[] arr;
    static int[] count;   // 값별 등장 횟수
    static int[] freq;    // 등장 횟수별 개수
    static int maxFreq;
    static int sqrtN;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        Query[] queries = new Query[m];
        int[] answer = new int[m];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken()) - 1;
            int r = Integer.parseInt(st.nextToken()) - 1;
            queries[i] = new Query(l, r, i);
        }

        sqrtN = (int) Math.sqrt(n);
        count = new int[1000001];
        freq = new int[n + 1];
        maxFreq = 0;

        Arrays.sort(queries, (a, b) -> {
            int blockA = a.l / sqrtN;
            int blockB = b.l / sqrtN;

            if (blockA != blockB) {
                return blockA - blockB;
            }
            return a.r - b.r;
        });

        int curL = 0;
        int curR = -1;

        for (Query q : queries) {
            while (curL > q.l) add(arr[--curL]);
            while (curR < q.r) add(arr[++curR]);
            while (curL < q.l) remove(arr[curL++]);
            while (curR > q.r) remove(arr[curR--]);

            answer[q.idx] = maxFreq;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            sb.append(answer[i]).append("\n");
        }

        System.out.print(sb);
    }

    static void add(int x) {
        int c = count[x];
        freq[c]--;
        count[x]++;
        freq[c + 1]++;

        maxFreq = Math.max(maxFreq, count[x]);
    }

    static void remove(int x) {
        int c = count[x];
        freq[c]--;
        count[x]--;
        freq[c - 1]++;

        if (freq[maxFreq] == 0) {
            maxFreq--;
        }
    }
}

 

---

📄 정리

• 구간 최빈값 문제 → Mo's Algorithm 필수 유형
• count + freq 2개 배열로 최빈값 유지
• add/remove 구현이 핵심