백준 2912 자바 - 백설공주와 난쟁이 (BOJ 2912 JAVA)

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

 

 

1.

  기본적인 아이디어는 각 쿼리의 [a, b] 구간에 대해 매번 [a, b] 전체를 확인하지 않고, 이전에 확인했던 구간과 겹치는 구간은 제외하고 확인하는 것이다. 예를들어 이전에 확인했던 구간이 [1, 100]이고 이번에 확인할 구간이 [4, 95]라고 해보자. 

  이 때, [1, 100] 구간을 전부 확인하면 100번 + [4, 95] 구간을 전부 확인하면 92번 봐야 한다. 그럼 192번 동작해야 한다. 하지만 [1, 100] 구간의 결과에서 [1, 3] 구간을 빼고, [96, 100] 구간을 빼면 [4, 95] 구간 전체를 본 것과 동일한 결과를 얻을 수 있다. 이 경우 108번만 동작하면 된다.

 

2.

  update가 없는 쿼리 문제이다. 따라서 쿼리 순서를 효율적으로 변경해 풀어도 된다. (offline query)

[a, b] 사이의 값들에 대한 구간 쿼리 이므로, '1'의 아이디어를 적용하여 쿼리의 순서를 최대한 이전과 많은 구간이 겹치게 하면 효율적으로 풀 수 있다. 이전과 최대한 많은 구간을 겹치게 쿼리의 순서를 바꾸는 것은 모스(Mo's) 알고리즘의 방식을 사용하면 된다. 'a / sqrt(n)'로 정렬 후 동일하다면 'b'로 정렬

 

 

3.

색상 최대치가 10000개 뿐이므로, 10000 크기의 배열에 모자 색상을 카운팅한다면, k/2보다 많은 색상의 모자는 단순히 각 쿼리마다 전체 배열을 확인해도 딱히 문제 없다. (O(10000*10000) -> 코드의 'getHatNum()'

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02900/BOJ_2912.java

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

class Picture implements Comparable<Picture> {
    int a, b, order;
    static int sqrtN;
    public Picture(int a, int b, int order) {
        this.a = a;
        this.b = b;
        this.order = order;
    }

    @Override
    public int compareTo(Picture o) {
        int a1 = this.a / sqrtN;
        int a2 = o.a / sqrtN;
        if (a1 == a2) return this.b - o.b;
        return a1-a2;
    }
}

public class Main extends FastInput {
    private int getHatNum(int[] cnt, Picture cur) {
        int target = (cur.b-cur.a+1)/2;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] > target) return i;
        }
        return -1;
    }

    private void solution() throws Exception {
        int n = nextInt();
        Picture.sqrtN = (int) Math.sqrt(n);
        int c = nextInt();

        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++)
            arr[i] = nextInt();

        int m = nextInt();
        int[] answer = new int[m];
        ArrayList<Picture> pic = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            pic.add(new Picture(nextInt(), nextInt(), i));
        }

        Collections.sort(pic);
        int[] cnt = new int[c+1];
        for (int i = pic.get(0).a; i <= pic.get(0).b; i++) {
            ++cnt[arr[i]];
        }
        answer[pic.get(0).order] = getHatNum(cnt, pic.get(0));

        for (int idx = 1; idx < pic.size(); idx++) {
            int curA = pic.get(idx).a;
            int curB = pic.get(idx).b;
            int befA = pic.get(idx-1).a;
            int befB = pic.get(idx-1).b;

            for (int i = befA; i < curA; i++) cnt[arr[i]]--;
            for (int i = curA; i < befA; i++) cnt[arr[i]]++;
            for (int i = befB+1; i <= curB; i++) cnt[arr[i]]++;
            for (int i = curB+1; i <= befB; i++) cnt[arr[i]]--;

            answer[pic.get(idx).order] = getHatNum(cnt, pic.get(idx));
        }

        StringBuilder output = new StringBuilder();
        for (int i = 0; i < m; i++) {
            if (answer[i] == -1) output.append('n').append('o');
            else output.append('y').append('e').append('s').append(' ').append(answer[i]);
            output.append('\n');
        }
        System.out.print(output);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}