[PGM]행렬의 곱셈

티어 : Lv. 2
정답여부 : 정답

💡문제

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.

제한 조건

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

 

💡입출력 예

 

💡문제 분석 요약 

• 각 입력받은 배열의 행렬의 곱셈을 구하면 되는 문제
• 행렬의 곱셈은 그림과 같이 같은색 형광팬이 같은 색깔과 수를 곱하면 되는 문제

 

💡알고리즘 설계

1. answer 행에는 arr1 길이를 열에는 arr2길이를 지정
2. 각 행과 열만큼 for문을 만들어 주고 arr1배열의 열과 arr2 배열의 행을 곱하여 answer 있는 값과 +하여 넣어줌
3. 출력

 

💡시간복잡도

• O(n3)

 

💡코드

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int row = arr1.length; // 행
        int col = arr2[0].length; // 열
        int[][] answer = new int[row][col]; // ex answer[3][2]
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = 0; k < arr1[0].length; k++) {
                    answer[i][j] += arr1[i][k] * arr2[k][j];
                }
            }
        }
        return answer;
    }
}

 

💡 틀린 이유

틀린건 없었고 행렬의 곱셈 구하는 공식을 찾아보았다.

answer에 굳이 크기를 지정하지 않고 Array방식으로 구현하는 문제 풀이도 해보았다

 

💡 틀린 부분 수정 or 다른 풀이

class Solution {
    public ArrayList<ArrayList<Integer>> solution(int[][] arr1, int[][] arr2) {
        ArrayList<ArrayList<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < arr1.length; i++) {
            ArrayList<Integer> row = new ArrayList<>();
            for (int j = 0; j < arr2[0].length; j++) {
                int sum = 0;
                for (int k = 0; k < arr1[0].length; k++) {
                    sum += arr1[i][k] * arr2[k][j];
                }
                row.add(sum);
            }
            answer.add(row);
        }

        return answer;
    }
}

 

💡 느낀점 or 기억할정보

행렬의곱셈 저번에도 풀어본거 같은데 DP방식으로 풀수 있는지 궁금하다.