[백준] 5549번 행성 탐사 JAVA 풀이
나의 풀이
문제를 읽고나서 시간 복잡도를 보고 누적합 알고리즘을 사용하면 되겠다는 아이디어는 바로 떠올랐다. 하지만 처음에는 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);
}
}
}
Author And Source
이 문제에 관하여([백준] 5549번 행성 탐사 JAVA 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hahahaa8642/백준-5549번-행성-탐사-JAVA-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)