알고리즘 문제로 알아보는 Clever trick

코드에서 Clever trick 제거하기

 

-

알고리즘 문제 풀이에 대해 '클레버한 트릭'이라는 피드백을 받아 리팩토링 하는 경험을 했다.

이 단어를 처음 듣기도 했고, 최종 개선된 풀이가 신선한 느낌이 들어 포스팅 소재로 기록해본다.

---

Clever trick

이 단어를 프로그래밍적으로 해석했을 때 좋게 표현하면 문제를 해결하기 위한 획기적이고 창의적인 방법이고, 나쁘게 표현하면 가독성이 떨어지고 유지보수가 어려운 속임수라고 할 수 있다.

---

문제

백준 문제 바로 가기

---

첫 번째 풀이

const [input, ...lines]: string[] = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const [N, M] = input.split(' ').map(Number);
const [maxN, maxM] = [N - 8, M - 8];
const MAX_COUNT = 64;
const board = lines.map((line) => line.split(''));

const white = ['WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW'];
const black = ['BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB', 'BWBWBWBW', 'WBWBWBWB'];

const calcMismatch = (r: number, c: number) => {
    let checkWhite = 0;
    let checkBlack = 0;

    for (let i = r; i < r + 8; i++) {
        for (let j = c; j < c + 8; j++) {
            if (board[i][j] !== white[i - r][j - c]) checkWhite++;
            if (board[i][j] !== black[i - r][j - c]) checkBlack++;
        }
    }

    return Math.min(checkWhite, checkBlack);
};

const getMinChangeCount = (max: number) => {
    let minCount = max;
    for (let i = 0; i <= maxN; i++) {
        for (let j = 0; j <= maxM; j++) {
            minCount = Math.min(minCount, calcMismatch(i, j));
        }
    }
    return minCount;
};

 

처음 제출했던 풀이도 괜찮지만 `white`와 `black`을 미리 만들지 않고 풀 수 있는 방법을 써보라는 피드백을 받았다.

---

두 번째 풀이 - 트릭

const countMinDiffer = (r: number, c: number) => {
    const count: Record<string, number> = {
        white: 0,
        black: 0,
    };

    for (let i = r; i < r + 8; i++) {
        for (let j = c; j < c + 8; j++) {
            const val = board[i][j];
            let color = '';
            if ((i + j) % 2 === 0) {
                color = val === 'W' ? 'white' : 'black';
            } else {
                color = val === 'B' ? 'white' : 'black';
            }
            count[color] += 1; //check
        }
    }
    return Math.min(count.white, count.black);
};

 

새로운 풀이의 if문은 짝수가 `W` 홀수가 `B`인 `white` 체스판을 기준으로 카운트한다. 순회 후 `checkWhite`의 값이 더 적으면 `black` 체스판을 만들기 위한 최솟값이 되고, `checkBlack`의 값이 더 적으면 `white` 체스판을 만들기 위한 최솟값이 된다. 즉, `white` 체스판을 완성하는데 필요한 색상별 변경수를 세는 방법이다.

 

이 풀이에 대해 check 표시가 되어 있는 부분에서 클레버한 트릭 이라는 피드백을 받았다. 

---

세 번째 풀이

let을 없애고, expectedColor란 변수를 도입한다.

 

힌트를 받아 아주 정직한 풀이를 만들어냈다. `expectedColor`를 매개변수로 받는다. 호출하는 곳에서 `W` 혹은 `B`를 전달하면 그 색상에 맞는 체스판을 만들기 위한 변경수를 체크하는 방식이다.

 

이 문제도 if문 부분에서 고민을 많이 했다.

중복이 너무 뻔히 보이는데 이렇게 빼도, 저렇게 빼도 이 코드 외에는 통과를 하지 못해서 최선이라는 생각으로 제출했다.

---

🍯 힌트와 최종 풀이

const expectedColor = (i + j) % 2 === 0 ? "B" : "W"

 

특정 컬러를 정해서 만드는 풀이까지는 갔지만 짝수/홀수를 판단하는 if문에 적용할 생각을 못했다. 이전 코드가 클레버한 트릭인지 느껴진다. 풀이가 훨씬 간결해지고 가독성이 좋아졌다. 특히 이중 for문 내에서 어떤 값을 구하려고 하는지 의미가 명확하다. 풀이 방향성은 동일한데 이렇게 다른 코드가 될 수 있다는 점에 또 한 번 놀랐다. 분명 제출 전까지 중복을 줄일 수 있을 것 같아 고민을 많이 했는데 생각해 내지 못한 점이 아쉽기도 하다. 다음에도 중복 제거의 기운을 느끼지만 분리가 되지 않을 때는 이 풀이를 떠올려 보자. 분기 조건이 될 수 있는 고정값을 찾아 변수에 담는 방법을 기억해 활용해야겠다.