프로그래머스 [Lv. 3] 2차원 동전 뒤집기 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(beginning, target) {
    let minV = 21;
    const n = beginning.length;
    const m = beginning[0].length;
    const selectedRows = [];
    const selectedCols = [];
    
    // 배열이 일치하는지 확인하는 함수
    const isCorrect = (newBoard) => {
        for (let r = 0; r < n; r++) {
            for (let c = 0; c < m; c++) {
                if (newBoard[r][c] != target[r][c]) {
                    return false;
                }
            }
        }
        return true;
    }
    
    // 만들어진 조합을 바탕으로 보드를 만들고 확인하는 함수
    const checkBoard = (selectedRow, selectedCol) => {
        const cnt = selectedRow.length + selectedCol.length;
        if (cnt >= minV) {
            return
        }
        let newBoard = beginning.map((e) => [...e]);
        for (const sr of selectedRow) {
            for (let c = 0; c < m; c++) {
                newBoard[sr][c] = (newBoard[sr][c] + 1) % 2;
            }
        }
        
        for (const sc of selectedCol) {
            for (let r = 0; r < n; r++) {
                newBoard[r][sc] = (newBoard[r][sc] + 1) % 2;
            }
        }
        // 확인
        if (isCorrect(newBoard)) {
            minV = cnt;
        }
    }
    // 조합 만들어주는 함수
    const combinations = (idx, selected, range, what) => {
        if (idx == range) {
            if (what == "row") {
                selectedRows.push(selected);
            } else if (what == "col") {
                selectedCols.push(selected);
            }
            return
        }
        combinations(idx+1, [idx, ...selected], range, what);
        combinations(idx+1, selected, range, what);
    }
    combinations(0, [], n, "row");
    combinations(0, [], m, "col");
    
    // 확인하기
    for (const selectedRow of selectedRows) {
        for (const selectedCol of selectedCols) {
            checkBoard(selectedRow, selectedCol);
        }
    }
    const answer = minV == 21 ? -1 : minV;
    return answer;
}

풀이 방법

 

1. 행과 열의 조합 생성: 먼저, 뒤집을 수 있는 모든 행과 열의 조합을 생성한다. 예를 들어, 첫 번째 행을 뒤집거나, 두 번째 열을 뒤집는 등의 조합을 만들어 낸다.
2. 조합을 통한 배열 변환: 생성된 행과 열의 조합을 사용해, beginning 배열을 뒤집어 새로운 배열을 만다. 행을 뒤집는 것은 해당 행의 모든 요소를 반전시키는 것이고, 열을 뒤집는 것은 해당 열의 모든 요소를 반전시킨다.
3. 변환된 배열과 target 배열 비교: 변환된 배열이 target 배열과 일치하는지 확인한다. 일치한다면, 이때 뒤집은 행과 열의 개수를 계산하여, 가장 적은 횟수로 이루어진 조합을 기록한다.
4. 결과 반환: 모든 조합을 확인한 후, 가장 적은 횟수로 beginning을 target과 동일하게 만든 경우를 반환한다. 만약 어떤 조합으로도 일치시킬 수 없다면, -1을 반환한다.

 

느낀점

• 처음에는 순서가 중요한 줄 알고 안될 줄 알았는데 조합으로 풀 수 있다는 것을 알고 연산 횟수를 간략하게 계산하면 다음과 같다.
  • 2^10 * 2^10 * 10^2 = 1024 * 1024 * 100 = 104,857,600 ??? 사실 어떻게 된거지
  • 시간 복잡도 = O(2^n * 2^m * n * m)