8. 프로그래머스 - 행렬의 곱셈 (배열)

문제 설명
2차원 행렬 arr1과 arr2가 주어졌을 때, arr1에 arr2를 곱한 결과를 반환하는 함수를 완성하세요.

제한 조건

• 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
• 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 정수입니다.
• 곱할 수 있는 형태의 배열만 입력으로 주어집니다.
  (즉, arr1의 열의 수는 arr2의 행의 수와 같습니다.)

입출력 예

arr1	arr2	return
[[1, 4], [3, 2], [4, 1]]	[[3, 3], [3, 3]]	[[15, 15], [15, 15], [15, 15]]
[[2, 3, 2], [4, 2, 4], [3, 1, 4]]	[[5, 4, 3], [2, 4, 1], [3, 1, 1]]	[[22, 22, 11], [36, 28, 18], [29, 20, 14]]

---

• arr1: 크기 = a×ba \times ba×b
• arr2: 크기 = b×cb \times cb×c
• 결과 행렬: 크기 = a×ca \times ca×c

즉, arr1의 행과 arr2의 열을 곱해서 결과의 해당 위치에 채워 넣는 방식이다.

 

핵심 로직

result[i][j] = arr1[i][0] * arr2[0][j]
             + arr1[i][1] * arr2[1][j]
             + ...
             + arr1[i][k] * arr2[k][j];

result[i][j]는 arr1의 i번째 행과 arr2의 j번째 열을 하나하나 곱해서 더한 값이다.

 

알고리즘 코드

public class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int n = arr1.length;         // arr1 행 수
        int k = arr1[0].length;      // arr1 열 수 = arr2 행 수
        int m = arr2[0].length;      // arr2 열 수

        int[][] result = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int kIdx = 0; kIdx < k; kIdx++) {
                int a = arr1[i][kIdx];
                for (int j = 0; j < m; j++) {
                    result[i][j] += a * arr2[kIdx][j];
                }
            }
        }

        return result;
    }
}

 

시간 복잡도 분석

O(n×k×m)이다.