[프로그래머스] 행렬의 곱셈 (JAVA)

링크

https://school.programmers.co.kr/learn/courses/30/lessons/12949go

프로그래머스

 

문제 요약

2차원 행렬 arr1과 arr2를 곱한 결과 반환하기

 

제한

• 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
• 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
• 곱할 수 있는 배열만 주어집니다.

 

풀이

행렬의 곱셈을 계산하는 방법을 살펴보면 다음과 같습니다.

1. arr1의 첫 번째 행과 arr2의 첫 번째 열의 원소들을 각각 곱한 후, 그 합을 구합니다. → 결과 행렬의 1행 1열 값이 됩니다.
2. arr1의 첫 번째 행과 arr2의 두 번째 열의 원소들을 각각 곱한 후, 그 합을 구합니다. → 결과 행렬의 1행 2열 값이 됩니다.
3. 동일한 방식으로 모든 행과 열에 대해 계산을 반복합니다.

arr1이 (N*L) 크기이고 arr2가 (L*M) 크기라면, 결과 행렬은 (N*M) 크기가 됩니다.

 

결과 행렬의 각 원소를 계산하려면 L번 곱셈한 후 마지막에 이 결과들을 합해야 합니다.

따라서 행렬 곱의 총 연산 횟수는 O(N*M*L)입니다.

주어진 제한 조건을 보면 N, M, L의 값은 모두 최대 100이므로, 최대 10^6번의 연산입니다.

 

코드

import java.util.*;
class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int N=arr1.length;
        int L=arr1[0].length;
        int M=arr2[0].length;
        int[][] answer = new int[N][M];

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                for(int k=0; k<L; k++){
                    answer[i][j] += arr1[i][k] * arr2[k][j];
                }
            }
        }
        return answer;
    }
}

[시간 복잡도]

• arr1: N*L 크기의 행렬
• arr2: L*M 크기의 행렬
• N,L,M의 범위는 모두 동일하므로 최종 시간 복잡도는 3중 for문으로 인해 O(N^3)