백준 13547 자바 - 수열과 쿼리 5 (BOJ 13547 JAVA)

문제 : boj13547

 

 

  문제에 비해 필요한 아이디어 및 구현과정은 상당히 복잡한 문제이므로 간단한 부분부터 차례대로 생각해보자.

 

1. 우선은 단건의 쿼리를 해결할 방법을 생각해보자.

  [Ai, Aj]에 존재하는 서로다른 수의 개수를 알 수 있어야 한다. 여러 방법이 있겠으나, 각 값을 표현할 메모리가 충분하다면 값의 최대 크기에 해당하는 배열을 만들어 해당 수가 나왔는지 체크하는 방법이 가장 효율적이다. 이 문제에서는 N개의 값 각각의 최대값은 1,000,000이므로 100만개짜리 boolean 배열만 있으면 된다.

 

  100만개짜리 배열 arr이 있고, cnt라는 변수를 뒀다고 해보자. 각 쿼리에서 i와 j를 입력받았을 때 Ai부터 Aj까지 

순회하며 배열에 체크한다. 이미 체크되어 있던게 아니라면 cnt를 증가시키면 된다. 그럼 서로 다른 수의 개수를 알 수 있다.

 

  예를들어 Ai부터 Aj까지의 실제 값이 [1, 1, 4, 2, 4] 이고 이 중에서 서로 다른 수의 개수를 찾아보자. arr은 다음과 같이 체크될 것이고, false에서 true로 변경될 때만 cnt를 세면 되므로 cnt = 3이 될 것이다.

   

 

2. 연속된 쿼리를 효율적으로 해결할 방법을 생각해보자.

  만약 모든 쿼리가 i가 1, j가 N이라고 해보자. 이 경우 '1'과 같이 각 건의 쿼리를 M번 처리할 경우, 각 M번에 대해 N번씩 체크해야 하므로 매우 비효율적일 것이다. 좀 더 효율적으로 해볼 수 있다.

 

  직전에 체크했었던 쿼리의 i가 3, j가 10이라고 해보자. 그리고 이번에 답을 구해야할 쿼리는 i가 5, j가 11이다. 그럼 직전 쿼리에서 했던 계산을 이용해서 이번 쿼리를 좀 더 효율적으로 구해볼 수 있지 않을까? 이전 구해둔 구간 [3, 10]의 결과에서 [5, 11] 결과는 [3, 5)를 제외하고, (10, 11]을 추가하면 가능하다. 이렇게 되면 [5, 11]을 새로 확인하는 경우보다 연산 횟수가 훨씬 줄어든다.

  만약 구간이 추가만 된다면 '1'에서 설정한 대로 boolean형의 배열로 판단 가능하다. 하지만 제외되는 경우, 없어지는 숫자는 제거되어야 한다. 이 부분을 처리하기 위해 '1'에서 설명한 arr 배열을 int형으로 변경해보자. 예시는 바로 위에서 든 예시인 [3, 10] 에서 [5, 11]로 변경되는 것으로 해보겠다. 실제 값은 다음과 같다.

 

  우선 [3, 10]에 대해 arr과 cnt를 확인해보자.

 

그럼 이제 [5, 11]을 확인해보자. 우선 [3, 5)를 제외할것이고, A_3 부터 제외한다. 다음과 같이 될 것이다.

다음으로 A_4를 제외할꺼다. 다음과 같이 될 것이다. 이와 같이 구간을 제외할 때 해당 수가 나타난 횟수가 1에서 0이 된다면 서로 다른 수의 종류(cnt)를 감소시키면 된다.

다음으로 (10, 11]을 추가해보자. A_11만 추가하면 되며, 다음과 같이 될 것이다. 이와 같이 구간을 추가할 때 해당 수가 나타난 횟수가 0에서 1이 된다면 서로 다른 수의 종류(cnt)를 증가시키면 된다.

 

3. 그럼 이제 시간을 줄여보자.

  '2'까지의 과정으로 이 문제를 좀 더 효율적으로 처리할 수 있었다. 하지만 이대로 한다면 여전히 '시간 초과'가 날 것이다. '2'에서 나왔던 이전 쿼리의 결과를 활용하는 방법을 사용할 때, 구간의 제거, 추가를 좀 더 효율적으로 처리해볼 수 있다.

 

  이 문제는 단 한종류의 쿼리만 존재한다. 따라서 쿼리가 들어왔던 순서만 따로 기록해둔다면, 임의로 쿼리의 순서를 변경해서 처리해도 아무런 문제가 없다. 따라서 범위의 제거, 추가가 더 적게 일어날 수 있도록 임의로 순서를 변경한다면 더 효율적으로 쿼리를 처리할 수 있을 것이다(오프라인 쿼리).

 

  예를들어 각 쿼리가 [1, 10], [10, 30], [1, 30]이라고 해보자. 당연하게도 들어온 순서대로 처리하는 것 보다는 [1, 10] -> [1, 30] -> [10, 30] 순서로 처리하는 것이 더 연산이 적다.

  

  제곱근 분할법(sqrt decomposition) 아이디어를 차용한 모스 알고리즘(mo's) 방식을 사용하면 위와 같은 쿼리를 효율적으로 정렬할 수 있다. 정렬 방식은 order by i/sqrt(N), j 이다. (각 쿼리의 i를 N의 제곱근으로 나눈 값, 각 쿼리의 j값 순서로 오름차순)

 

  제곱근 분할법과 모스 알고리즘에 대한 이해가 필요하다면 여기를 참고하면 된다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;

class Query implements Comparable<Query> {
    static double sqrtN;
    int a, b, factor, idx;

    public Query(int a, int b, int idx) {
        this.a = a;
        this.b = b;
        this.idx = idx;
        this.factor = (int)(a/sqrtN);
    }

    @Override
    public int compareTo(Query o) {
        if (this.factor == o.factor)
            return this.b - o.b;
        return this.factor - o.factor;
    }
}

public class Main extends FastInput {
    private int[] numCnt = new int[1000001];
    private int cnt = 0;

    private void push(int num) {
        if (++numCnt[num] == 1) cnt++;
    }
    private void pop(int num) {
        if (--numCnt[num] == 0) cnt--;
    }

    private void solution() throws Exception {
        int n = nextInt();
        Query.sqrtN = Math.sqrt(n);
        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++)
            arr[i] = nextInt();

        int m = nextInt();
        Query[] queries = new Query[m];
        for (int i = 0; i < m; i++)
            queries[i] = new Query(nextInt(), nextInt(), i);
        Arrays.sort(queries);

        int[] answer = new int[m];

        int prevA = queries[0].a;
        int prevB = queries[0].a-1;

        for (int i = 0; i < m; i++) {
            int curA = queries[i].a;
            int curB = queries[i].b;

            for (int k = prevA; k < curA; k++)      pop(arr[k]);
            for (int k = curA; k < prevA; k++)      push(arr[k]);
            for (int k = prevB+1; k <= curB; k++)   push(arr[k]);
            for (int k = curB+1; k <= prevB; k++)   pop(arr[k]);

            answer[queries[i].idx] = cnt;
            prevA = curA;
            prevB = curB;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++)
            sb.append(answer[i]).append('\n');
        System.out.print(sb);
    }

    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++];
    }
}