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

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

2차원 배열 arr1, arr2가 있을 때 이들의 행렬 곱을 구한 2차원 배열을 반환하는 함수를 작성하는 문제이다.

사실 이번 문제는 코딩이 어렵다기 보단, 행렬의 곱셈에 대해 제대로 알고 있는지 파악하는 것이 핵심이라고 생각한다.

첫번 째 예제 입력에 대한 행렬곱 과정은 다음과 같다.

arr1의 [1, 4]가 있으면, 이에 대한 곱셈을 arr2에 있는 각 열 [3, 3], [3, 3]에 대해 곱셈을 진행해야 한다.

프로그래밍에서 배열 선언의 특성 상 어쩔 수 없이 arr2도 [[3, 3], [3, 3]]과 같은 형태로 작성해야 하지만, 실제로 행렬 곱셈을 진행할 때는 열(column)끼리 곱해야 한다는 점에 유의해야한다.

만약 arr2가 [[5, 4], [2, 1]]인 경우 첫 번째 열인 (5, 2)를 먼저 곱하고 그 다음 (4, 1)에 대해 곱셈을 진행하여 서로 더해줘야 한다는 것이다.

따라서 이를 구현하기 위해 아래와 같이 3중 for문이 필요하다.

for (int i = 0; i < r1; i++) {
	for (int j = 0; j < c2; j++) {
		for (int k = 0; k < c1; k++) {
        	answer[i][j] += arr1[i][k] * arr2[k][j];
		}
	}
}

코드가 잘 이해되지 않는다면 i, j, k에 대입하는 값에 따라 설명한 아래 그림을 참고하길 바란다.

또한 왼쪽 행렬의 크기가 M x K이고 오른쪽 행렬의 크기가 K x N이라면 정답 행렬의 크기는 M x N 이므로 정답 배열의 크기는 아래와 같다.

int r1 = arr1.length;
int c2 = arr2[0].length;

int[][] answer = new int[r1][c2];

따라서 전체 문제풀이 코드는 다음과 같다.

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int r1 = arr1.length;
        int r2 = arr1[0].length;
        
        int c1 = arr2.length;
        int c2 = arr2[0].length;
        
        int[][] answer = new int[r1][c2];
        for (int i = 0; i < r1; i++) {
            for (int j = 0; j < c2; j++) {
                for (int k = 0; k < c1; k++) {
                    answer[i][j] += arr1[i][k] * arr2[k][j];
                }
            }
        }
        
        return answer;
    }
}