[백준] 22251 빌런 호석 (Javascript)

잭슨·2024년 4월 30일

구현 백준 알고리즘 자바스크립트

알고리즘 문제 풀이

목록 보기

76/130

문제

BOJ22251_빌런 호석

풀이

요구사항

엘리베이터 층수를 나타내는 디스플레이의 LED를 반전시켜 다른 층을 표현할 수 있는 경우의 수를 구하는 문제

하나의 숫자는 LED 7개를 사용하여 표시할 수 있고, 반전시킨다는 의미는 켜져있는 LED를 끄고, 꺼져있는 LED를 키는 작업을 말한다.

반전시킬 수 있는 LED의 최대개수는 정해져있다. 또한 반전시켰을 때 최대 층을 넘어가면 안된다.

해결방안

우선 LED에 켜져있는 부분과 꺼져있는 부분을 1과 0으로 배열에 담는다.

const led = [
    [1, 1, 1, 0, 1, 1, 1],
    [0, 0, 1, 0, 0, 1, 0],
    [1, 0, 1, 1, 1, 0, 1],
    [1, 0, 1, 1, 0, 1, 1],
    [0, 1, 1, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1, 1],
    [1, 1, 0, 1, 1, 1, 1],
    [1, 0, 1, 0, 0, 1, 0],
    [1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 0, 1, 1],
];

난 아래와 같이 번호를 매칭시켰다.

그리고 i번호에서 j번호가 되려면 LED를 몇 개 반전시켜야 하는지 구해서 새로운 2차원 배열에 저장한다.

const graph = Array.from({ length: 10 }, () => []);
let count;
for (let i = 0; i <= 9; i++) {
    for (let j = 0; j <= 9; j++) {
        count = 0;
        for (let k = 0; k < 7; k++) {
            if (led[i][k] !== led[j][k]) {
                count++;
            }
        }
        graph[i][j] = count;
    }
}

그런 다음 현재층과 1층부터 최대층까지 전부 비교하여 LED를 P번만 반전시켜서 만들 수 있는지 없는지 확인한다.

또한 예를 들어 입력으로 주어진 자릿수가 3자리라고 가정하고, 현재 층이 121층이라고 가정해보자. 1층과 121층을 비교하려는데 자릿수가 맞지 않아 비교하는 과정이 복잡해진다.

따라서 자릿수도 동일하게 맞춰주는 함수도 같이 만들어준다.

// i로 target을 만들 수 있는지 확인
function checkMakable(target, cur) {
    let count = 0;
    for (let i = 0; i < target.length; i++) {
        count += graph[target[i]][cur[i]];
    }
    // 반전 시킬 수 있는 최대 개수보다 많이 반전시켰다면
    if (count > P || count === 0) return false;
    return true;
}

// 자릿수 맞춰서 리턴해주는 함수
function getDigit(curFloor) {
    curFloor = String(curFloor).split('');
    const len = curFloor.length;
    const arr = Array(K - len).fill(0);
    // 자릿수 맞추기
    for (let i = 0; i < len; i++) {
        arr.push(+curFloor[i]);
    }
    return arr;
}

const currentFloor = getDigit(X);
let answer = 0;
for (let i = 1; i <= N; i++) {
    if (checkMakable(currentFloor, getDigit(i))) {
        answer++;
    }
}
console.log(answer);

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K, P, X] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const led = [
    [1, 1, 1, 0, 1, 1, 1],
    [0, 0, 1, 0, 0, 1, 0],
    [1, 0, 1, 1, 1, 0, 1],
    [1, 0, 1, 1, 0, 1, 1],
    [0, 1, 1, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1, 1],
    [1, 1, 0, 1, 1, 1, 1],
    [1, 0, 1, 0, 0, 1, 0],
    [1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 0, 1, 1],
];

const graph = Array.from({ length: 10 }, () => []);
let count;
for (let i = 0; i <= 9; i++) {
    for (let j = 0; j <= 9; j++) {
        count = 0;
        for (let k = 0; k < 7; k++) {
            if (led[i][k] !== led[j][k]) {
                count++;
            }
        }
        graph[i][j] = count;
    }
}

// i로 target을 만들 수 있는지 확인
function checkMakable(target, cur) {
    let count = 0;
    for (let i = 0; i < target.length; i++) {
        count += graph[target[i]][cur[i]];
    }
    // 반전 시킬 수 있는 최대 개수보다 많이 반전시켰다면
    if (count > P || count === 0) return false;
    return true;
}

// 자릿수 맞춰서 리턴해주는 함수
function getDigit(curFloor) {
    curFloor = String(curFloor).split('');
    const len = curFloor.length;
    const arr = Array(K - len).fill(0);
    // 자릿수 맞추기
    for (let i = 0; i < len; i++) {
        arr.push(+curFloor[i]);
    }
    return arr;
}

const currentFloor = getDigit(X);
let answer = 0;
for (let i = 1; i <= N; i++) {
    if (checkMakable(currentFloor, getDigit(i))) {
        answer++;
    }
}
console.log(answer);

개선

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, K, P, X] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const led = [
    [1, 1, 1, 0, 1, 1, 1],
    [0, 0, 1, 0, 0, 1, 0],
    [1, 0, 1, 1, 1, 0, 1],
    [1, 0, 1, 1, 0, 1, 1],
    [0, 1, 1, 1, 0, 1, 0],
    [1, 1, 0, 1, 0, 1, 1],
    [1, 1, 0, 1, 1, 1, 1],
    [1, 0, 1, 0, 0, 1, 0],
    [1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 0, 1, 1],
];
const costs = Array.from({ length: 10 }, () => Array(10).fill(0));
for (let i = 0; i <= 9; i++) {
    for (let j = 0; j <= 9; j++) {
        let count = 0;
        for (let k = 0; k < 7; k++) {
            if (led[i][k] !== led[j][k]) {
                count++;
            }
        }
        costs[i][j] = count;
    }
}

let answer = 0;
for (let i = 1; i <= N; i++) {
    let cost = 0;
    let [a, b] = [X, i];
    for (let j = 0; j < K; j++) {
        cost += costs[a % 10][b % 10];
        a = Math.floor(a / 10);
        b = Math.floor(b / 10);
    }
    if (cost <= P && cost > 0) answer++;
}
console.log(answer);