[BOJ/Java] 5549: 행성 탐사

문제

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

N x M (N과 M은 1~1,000) 크기의 J, O, I로 이루어진 정보의 지도가 주어진다.

해당 지도에서 (a, b) 좌표에서 (c, d) 좌표까지의 J, O, I의 개수를 카운트해야 한다.

조사 대상 영역 개수인 K가 1~100,000으로 매우 크다.

 

풀이

처음에는 이중 for문으로 풀었는데, 시간 초과가 발생했다. K의 범위를 간과했었다.

 

백준의 경우, 1초에 약 1억 번 정도의 연산이 가능하다고 한다. 즉, 시간 제한이 1초면 1억 번 정도를 계산할 수 있다. 이중 for문으로 연산했을 때 최악의 경우 약 1,000,000(N x M) x 100,000(K) = 10^11 즉, 1,000억 번의 연산이 필요하다.

 

그렇기에 누적 합을 사용해서 문제를 접근해야 했다. 이차원 배열에서의 누적 합은 처음 만나는 유형이어서 공부한 후 문제를 풀 수 있었다. 알고나니 공부할 필요없이 조금만 더 생각했으면 코드로 구현할 수 있었을 것 같다.

 

이차원 배열에서의 누적 합은 위쪽 누적 합 + 왼쪽 누적 합 - 중복된 좌상단 값으로 구할 수 있다.

psumJ[i][j] = psumJ[i-1][j]       // 위쪽
            + psumJ[i][j-1]       // 왼쪽
            - psumJ[i-1][j-1]     // 중복으로 더한 좌상단

 

문제를 풀면서, StringBuilder의 append 메서드를 여러번 호출하는 것보다 대부분의 상황에서 하나의 StringBuilder에 append 메서드를 체이닝해서 작성하는 것이 효율적이라는 것을 새로 알게 되었다.

 

처음엔 이렇게 작성했었다.

sb.append(jCount + " " + oCount + " " + iCount);
sb.append("\n");

 

그런데 메서드 체이닝으로 작성한 코드가 기존 코드보다 100ms 이상 빨랐다.

sb.append(jCount).append(" ").append(oCount).append(" ").append(iCount).append("\n");

 

아래는 기존 코드의 채점 결과, 위는 메서드 체이닝으로 작성한 코드의 채점 결과다.

 

append 메서드는 항상 자기 자신(this)을 반환한다. 따라서 메서드 체이닝을 사용할 수 있는데, 메서드 체이닝을 사용하면 sb 객체에서 append 메서드가 연속적으로 실행되고, 중간 결과를 저장하거나 스택에 올리지 않아 성능상의 이점이 있다.

 

더욱이 기존의 코드에서는 인자로 문자열 결합 연산이 수행되기 때문에, 내부적으로 JVM이 표현식을 처리하기 위해 새로운 StringBuilder 객체를 생성해서 toString 메서드로 문자열로 만든 다음, 다시 원래 sb.append(...)에 넣게 되면서 불필요한 연산이 생기면서 실행 시간이 늘어나게 되었다.

 

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, m, k;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(br.readLine());
        char[][] planet = new char[n + 1][m + 1];
        int[][] accSumJ = new int[n + 1][m + 1];
        int[][] accSumO = new int[n + 1][m + 1];
        int[][] accSumI = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            String info = br.readLine();
            for (int j = 1; j <= m; j++) {
                planet[i][j] = info.charAt(j-1);
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char info = planet[i][j];
                int isJ = info == 'J' ? 1 : 0;
                int isO = info == 'O' ? 1 : 0;
                int isI = info == 'I' ? 1 : 0;
                // 현재 좌표에서 위쪽 누적 합, 왼쪽 누적 합을 더하고 중복으로 더한 좌상단 값을 빼준다.
                accSumJ[i][j] = accSumJ[i-1][j] + accSumJ[i][j-1] - accSumJ[i-1][j-1] + isJ;
                accSumO[i][j] = accSumO[i-1][j] + accSumO[i][j-1] - accSumO[i-1][j-1] + isO;
                accSumI[i][j] = accSumI[i-1][j] + accSumI[i][j-1] - accSumI[i-1][j-1] + isI;
            }
        }

        StringBuilder sb = new StringBuilder();
        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken());
            // 현재 좌표의 위쪽 부분합, 왼쪽 부분합을 빼주고 중복해서 뺀 값을 더해준다.
            int jCount = accSumJ[c][d] - accSumJ[a-1][d] - accSumJ[c][b-1] + accSumJ[a-1][b-1];
            int oCount = accSumO[c][d] - accSumO[a-1][d] - accSumO[c][b-1] + accSumO[a-1][b-1];
            int iCount = accSumI[c][d] - accSumI[a-1][d] - accSumI[c][b-1] + accSumI[a-1][b-1];

            sb.append(jCount).append(" ").append(oCount).append(" ").append(iCount).append("\n");
        }

        System.out.println(sb);
    }
}