be programmer
28438 : 행렬 연산(행렬 계산하기) - JAVA 본문
https://www.acmicpc.net/problem/28438
행렬의 행과 열을 입력받고 해당되는 쿼리에 맞게 그 부분을 더하면 된다.
어려운 연산이 없고 시간 제한이 n x m <= 50만에 3초라서 당초에는 그냥 2차원 배열을 만들고 해당 값들을 이차원 배열에 더해주면 되는 단순 구현 문제인줄 알았다.
하지만 그렇게 푸니 시간초과가 났다.
다음은 내가 처음 제출했던 방식이다.
while(q-- > 0){
st = new StringTokenizer(br.readLine());
int query = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if(query == 1){
for(int i = 0; i < m; i++){
map[r-1][i] += v;
}
}
else{
for(int i = 0; i < n; i++){
map[i][r-1] += v;
}
}
}
가장 최악의 케이스인 50만이나 되는 넓이의 행렬에 쿼리도 50만이라 가정할때 내가 짠 알고리즘대로 하나하나 더하며 행렬을 갱신한다 생각해보니 3초안에 해당 테스트 케이스가 통과되는것은 말이 안됐다. 해당 알고리즘대로라면 50만*50만번 진행된다.
그래서 시간복잡도를 줄이고자 다른 방법을 생각해봤다.
일차원 배열을 두개 만들어서, 행 덧셈 담당, 열 덧셈 담당으로 역할을 정하고, 덧셈을 하면 최적화가 가능했다.
왜냐하면 넓이가 4x4인 정의된 행렬이 있다고 가정했을 때,
행 배열[4]에 3 값이 들어오면 4행에는 모두 3이 들어가고, 이는 4행에는 전부 3을 집어넣어도 된다는
의미와 같기 때문이고, 열 배열[3]에 3 값이 들어와도 결국 3열에는 모두 3이 집어넣어진다는 의미고
양쪽이 겹치는 4행 3열의 문제는 쿼리가 끝나고 출력부분에서 행 결과 및 열 결과를 더하는 처리를 하
면 4행의 3과 3행의 4 모두 한번에 처리가 되어 중복 처리가 되는 부분이 방지가 되고, 빠른 출력인 bw
를 통해 시간도 절약이 되는 일석이조 효과로 통과할 수 있어 보였다.
그러니까
질의 부분에서는 일차원 배열에 0 0 0 3(행 배열), 0 0 3 0(열 배열)로 정의해서 해당 부분을
시간복잡도를 O(n^2)가 아닌 O(n)으로 줄이고,
결과 도출 과정에서 O(n^2)가 되지만 중복된 부분 없이 한번씩만 진행되게끔 했다.
앞선 예시에서는
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
bw.write(col[i] + row[j] + " ");
}
bw.write('\n');
}와 같고
0 0 0 3
0 0 0 3
3 3 3 6
0 0 0 3 이 각각 중복없이 출력만 되는 형태이다.
이 부분들을 나타낸 핵심 소스코드는 다음과 같다.
while(q-- > 0){
st = new StringTokenizer(br.readLine());
int query = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if(query == 1){
row[r-1] += v;
}
else{
col[r-1] += v;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
bw.write(row[i] + col[j] + " ");
}
bw.write("\n");
}
행 배열 열 배열을 구해서 값 입력 부분에서 중복 처리를 없에고, 출력부분에서 연산을 하도록 했다.
그러니 통과가 되었다.
다음은 소스코드이다.
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
int[] row = new int[n];
int[] col = new int[m];
while(q-- > 0){
st = new StringTokenizer(br.readLine());
int query = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if(query == 1){
row[r-1] += v;
}
else{
col[r-1] += v;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
bw.write(row[i] + col[j] + " ");
}
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
14938 : 서강그라운드 - JAVA (1) | 2024.06.12 |
---|---|
30804 : 과일 탕후루 - JAVA (0) | 2024.06.07 |
1208 : 부분수열의 합 2 - JAVA (0) | 2024.05.31 |
7902 : 등수 매기기 - JAVA (0) | 2024.05.31 |
15594 : Out of Place - JAVA (0) | 2024.05.31 |