[Java] 프로그래머스(level-2) - 행렬의 곱셈

입출력 예시

Input-1
arr1 = [[1, 4], [3, 2], [4, 1]]
arr2 = [[3, 3], [3, 3]]
Output-1
[[15, 15], [15, 15], [15, 15]]

Input-2
arr1 = [[2, 3, 2], [4, 2, 4], [3, 1, 4]]
arr2 = [[5, 4, 3], [2, 4, 1], [3, 1, 1]]
Output-2
[[22, 22, 11], [36, 28, 18], [29, 20, 14]]

문제 풀이

이 문제는 2차원 배열을 익숙하게 어느정도 다룰 수 있아야 한다.
먼저 행렬의 곱셈의 경우 아래 조건을 충족해야 한다.

• arr1(앞)의 열과 arr2(뒤)의 행이 같아야 한다.

// arr1(3X2)
1 4
3 2
4 1

// arr2(2X2)
3 3
3 3

예제로 주어진 arr1과 arr2를 보면 arr1(3X2)의 열과 arr2(2X2)의 행이 같음을 알 수 있다.

1X3+4X3 1X3+4X3
3X3+2X3 3X3+2X3
4X1+1X3 4X1+1X3

그리고 arr1의 행과 arr2 열별로 곱한 값을 더하면 각 행별로 곱한 결과를 구할 수 있다.

그럼 코드로 작성해보자.
먼저 행렬의 곱 결과를 저장할 2차원 배열 answer를 초기화 하자.

int[][] answer = new int[arr1.length][arr2[0].length];

그리고 반복문을 활용하여 행렬의 곱셈을 구현해볼 것이다.

arr1 = [[2, 3, 2], [4, 2, 4], [3, 1, 4]]	
arr2 = [[5, 4, 3], [2, 4, 1], [3, 1, 1]]	

answer[0][0] = 2X5 + 3X4 + 2X3
answer[0][1] = 2X2 + 3X4 + 2X1
answer[0][2] = 2X3 + 3X1 + 2X1
...

위 연산을 통해 arr1의 행이 arr2의 모든 열에 접근해야 함을 알 수 있다.
앞서 언급한 arr1의 열과 arr2의 행의 개수가 같다는 조건을 이용하여 반복문을 작성해보자.

for(int i=0; i<arr1.length; i++) {
    for(int j=0; j<arr2[0].length; j++) {
        int multi = 0;
        for(int k=0; k<arr2.length; k++) {
            multi += arr1[i][k] * arr2[k][j]; 
            answer[i][j] = multi;
        }
    }
}

위 코드의 k는 arr1의 열이자 arr2의 행으로 보면 되고, answer[i][j] += arr1[i][k] * arr2[k][j]라는 식으로 표현할 수 있다.

작성 코드

class Solution {
    public static void main(String[] args) {
        
        // int[][] arr1 = {{1,4},{3,2},{4,1}};
        // int[][] arr2 = {{3,3},{3,3}};
        int[][] arr1 = {{2,3,2},{4,2,4},{3,1,4}};
        int[][] arr2 = {{5,4,3},{2,4,1},{3,1,1}};
        
        long start = System.currentTimeMillis();
        solution(arr1, arr2);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }
    
    public static int[][] solution(int[][] arr1, int[][] arr2) {
        int[][] answer = new int[arr1.length][arr2[0].length];
        for(int i=0; i<arr1.length; i++) {
            for(int j=0; j<arr2[0].length; j++) {
                int multi = 0;
                for(int k=0; k<arr2.length; k++) {
                    multi += arr1[i][k] * arr2[k][j]; 
                    answer[i][j] = multi;
                }
            }
        }
        return answer;
    }
}

회고

• 먼저 행렬의 곱셈이 제대로 기억나지 않아 다시 공부하였고, 행렬의 곱을 위해 2차원 배열의 행과 열을 다룰 줄 알아야 하는데, 미숙해서 반복문을 작성하는 것이 어려웠다.

참고 문서

• 행렬의 곱셈 참조문서 출처