백준 14846 JAVA : 직사각형과 쿼리

문제

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

14846번: 직사각형과 쿼리

 

풀이 예상

백준 1749 점수따먹기풀이 와 같이 2차원 배열의 누적합을 활용해서 3차원으로 늘린 풀이 방법이다.

행렬의 원소의 범위가 1~10이였기 때문에 가능한 풀이이고 2차원과 방법은 똑같고 2차원 배열에 하나를 더 붙혀서 1~10숫자의 카운트를 각각해주면 된다.

 

풀이방법 (접근 방법 & 시간복잡도)

시간복잡도 => O(N^2)

 

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

public class Main {
    static int[][][] arr;
    static int N;
    static int[] answer;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1][11]; //1,1 ~ i,j 까지의 특정 숫자 개수

        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int num = Integer.parseInt(st.nextToken());
                for (int k = 1; k <= 10; k++) {
                    //자신 기준 왼쪽 + 위쪽 - 왼쪽위대각선
                    arr[i][j][k] = arr[i-1][j][k] + arr[i][j-1][k] - arr[i-1][j-1][k];
                }
                arr[i][j][num]++; //본인 숫자에 증가
            }
        }

        int Q = Integer.parseInt(br.readLine());
        for (int q = 0; q < Q; q++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            solution(x1,y1,x2,y2);
        }

        System.out.println(sb);

    }
    static void solution(int x1, int y1, int x2, int y2) {
        int result = 0;
        answer = new int[11];
        for (int i = 1; i <= 10; i++) {
            answer[i] = arr[x2][y2][i];
            answer[i] -= arr[x2][y1-1][i];
            answer[i] -= arr[x1-1][y2][i];
            answer[i] += arr[x1-1][y1-1][i];
        }

        for (int i = 1; i <= 10; i++) {
            if(answer[i] > 0) {
                result++;
            }
        }
        sb.append(result).append("\n");

    }
}

 

결과