나의 풀이

문제를 읽고나서 시간 복잡도를 보고 누적합 알고리즘을 사용하면 되겠다는 아이디어는 바로 떠올랐다. 하지만 처음에는 jungle, ocean, ice 2차원 배열을 각각 선언하고 3개의 배열을 각각 누적합해줘서 시간 초과가 났다.

해결책은 3개의 2차원 배열을 3차원 배열으로 만들면 된다. 3중 for문이 존재하므로 시간 복잡도가 오래 걸리지 않을까 생각이 들 수도 있지만, O(m*n*3) = O(m*n)일 뿐이다.

2차원 이상의 누적합에서는 반드시 배열에 padding을 넣어주도록 하자. 그래야 누적합을 진행하는 for문에서 인덱스 에러없이 손쉽게 코드를 짤 수 있다.

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

class Main {

    static int[][][] graph;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());
        graph = new int[m + 2][n + 2][3];
        for (int i = 0; i < m; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < n; j++) {
                switch (chars[j]) {
                    case 'J':
                        graph[i + 1][j + 1][0] = 1;
                        break;
                    case 'O':
                        graph[i + 1][j + 1][1] = 1;
                        break;
                    case 'I':
                        graph[i + 1][j + 1][2] = 1;
                        break;
                }
            }
        }

        for (int i = 1; i < m + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                for (int l = 0; l < 3; l++) {
                    graph[i][j][l] += graph[i - 1][j][l];
                }
            }
        }

        for (int i = 0; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                for (int l = 0; l < 3; l++) {
                    graph[i][j][l] += graph[i][j - 1][l];
                }
            }
        }

        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            int r1 = Integer.parseInt(st.nextToken());
            int c1 = Integer.parseInt(st.nextToken());
            int r2 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 3; i++) {
                sb.append(
                    graph[r2][c2][i] - graph[r1 - 1][c2][i] - graph[r2][c1 - 1][i] + graph[r1 - 1][
                        c1 - 1][i]).append(" ");
            }
            System.out.println(sb);
        }
    }
}