[프로그래머스] 행렬의 곱셈 (JavaScript) | 교공 알고리즘 스터디 47주차 - 1

행렬의 곱셈 | 문제 바로가기

⭐ 풀이의 핵심

행렬곱을 구하는 방법을 구현하면 되는 아주 심플한 문제였다
다만 아직도 익숙하지 않은 JavaScript의 reduce문을 복습하기 위해 기록을 남긴다

• 행렬 곱의 특징
  • 두 행렬 A, B가 있을 때 A 행렬의 열의 개수와 B 행렬의 행의 개수가 같아야 연산 가능
  • 곱셈 결과 나오는 행렬의 크기는 A 행렬의 행의 개수 * B 행렬의 열의 개수
  • 행렬 A의 i행의 원소들과 행렬 B의 j열의 원소들을 각각 대응하는 것끼리 곱하여 더한 것을 구함
  • ex)

🔽 for문을 활용한 풀이

const solution = (arr1, arr2) => {
    const r1 = arr1.length; // arr1 행 개수
    const c1 = arr1[0].length; // arr1 열 개수 (== arr2 행 개수)
    const c2 = arr2[0].length; // arr2 열 개수
    
    // 결과 배열의 크기는 r1 * c2
    let answer = new Array(r1);
    for (let i=0; i<r1; i++) {
        answer[i] = new Array(c2);
    }
    
    // arr1의 행마다 arr2의 열의 개수만큼 연산을 진행
    for (let i=0; i<r1; i++) {
        for (let j=0; j<c2; j++) {
            let value = 0;
            for (let k=0; k<c1; k++) {
                // arr1의 i행에서 열의 인덱스 == arr2의 j열에서 행의 인덱스인 같은 원소끼리 곱하여 더해주기
                value += arr1[i][k] * arr2[k][j];    
            }
            answer[i][j] = value;
        }
    }
    
    return answer;
}

3중 for문을 활용해 행렬곱의 연산 방식을 그대로 구현한 풀이.. 나는 이렇게 풀었다!
(자세한 설명은 주석 참고)
행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다. 라는 조건으로
O(N^3) = 100 * 100 * 100 정도로 충분하기 때문에 for문으로 고민보다 고..!

🔽 map 및 reduce 메서드를 활용한 풀이

const solution = (arr1, arr2) => {
    // arr1의 행마다
    return arr1.map((row) =>
        // arr2의 열의 개수만큼 연산을 진행
        arr2[0].map((_, cIdx) =>
            // arr1의 i행에서 열의 인덱스 == arr2의 j열에서 행의 인덱스(rIdx)인 같은 원소끼리 곱하여 더해주기
            // acc는 reduce문으로 더해지는 값을 저장하는 누산기 변수
            // cur은 arr1의 한 행의 현재 값으로 첫 번째 for문을 활용한 풀이에서 arr1[i][k]와 같은 값을 가리킴
            // arr2[rIdx][cIdx]는 첫 번째 for문을 활용한 풀이에서 arr2[k][j]와 같은 값을 가리킴
            row.reduce((acc, cur, rIdx) =>
                acc + cur * arr2[rIdx][cIdx]
            , 0)
        )
    );
}

[다른 사람의 풀이] 를 눌러보고 가히 충격적이었던 숏코딩..
🚨 하지만 map과 reduce문은 for문 보다 오래 걸리기 때문에
역시나 시간은 평균적으로 더 걸리는 것으로 나타났다
그래도 코드의 간결성을 높여주는 JavaScript의 좋은 메서드니까.. 기록!

📝 유용한 JavaScript 메서드 정리

• Array.reduce()
  • Array.reduce(callback[, initialValue])
  • 리듀서 callback 함수 인자
    • 누산기 (acc): 콜백의 반환값을 누적
    • 현재 값 (cur): 현재 처리할 요소
    • 현재 인덱스 (idx): 현재 처리할 요소의 인덱스 (initialValue를 제공한 경우 0, 아니면 1부터 시작)
    • 원본 배열 (src): reducer()를 호출한 배열
  • [참고] Array.reduce() - JavaScript | MDN
  • ex)

const arr = [1, 2, 3, 4];

const sumWithInitial = arr.reduce((acc, cur, idx) => {
  console.log(acc, cur, idx);
  return acc + cur;
}, 0);
// 0 1 0
// 1 2 1
// 3 3 2
// 6 4 3
console.log(sumWithInitial); // 10

const sumWithoutInitial = arr.reduce((acc, cur, idx) => {
  console.log(acc, cur, idx);
  return acc + cur;
});
// 1 2 1
// 3 3 2
// 6 4 3
console.log(sumWithoutInitial); // 10


/* reduce로 map 구현하기 */
const arr = [1, 2, 3, 4];

// ex. 배열의 요소가 홀수일 경우 "홀수", 짝수일 경우 "짝수" 반환
const result = arr.reduce((acc, cur) => {
  acc.push(cur % 2 ? "홀수" : "짝수");
  return acc;
}, []);

console.log(result); // ["홀수", "짝수", "홀수", "짝수"]
/***********************/


/* reduce로 filter 구현하기 */
const arr = [1, 2, 3, 4];

// ex. 배열의 요소가 홀수인 경우만 필터링
const result = arr.reduce((acc, cur) => {
  if (cur % 2) acc.push(cur);
  return acc;
}, []);

console.log(result); // [1, 3]
/**************************/