Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
Tags
more
Archives
Today
Total
관리 메뉴

be programmer

28438 : 행렬 연산(행렬 계산하기) - JAVA 본문

알고리즘/문제풀이

28438 : 행렬 연산(행렬 계산하기) - JAVA

mm______m 2024. 6. 4. 13:21

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