브루트 포스


2798번 (블랙잭)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const numbers = input[1].split(' ').map(Number);
let answer = 0;
let dif = M;
let sum = 0;
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (i === j) {
j++;
}
for (let k = 0; k < N; k++) {
if (k === i || k === j) {
k++;
}
sum = numbers[i] + numbers[j] + numbers[k];
if (sum > M) {
sum = 0;
}
if (dif > M - sum) {
dif = M - sum;
answer = sum;
}
}
}
}
console.log(answer);
  • 브루트 포스 알고리즘이라고 해서 시간복잡도를 아예 신경 쓰지 않았는데 이렇게 해도 되나 싶은 마음이 든다(..)
  • 3중 for문을 돌리고 같은 카드를 중복 선택할 수 없으므로 j를 돌릴 때에는 i와 같으면 스킵하고, k를 돌릴 때에는 i또는 j와 같으면 스킵했다.
  • sum에 3가지 숫자의 합을 넣고 M에서 sum을 뺀 값이 현재 가장 적은 차이가 나는 dif의 값보다 작으면 dif를 갱신하고 정답에 해당 값을 넣어준다.
  • 3가지 숫자의 합이 M을 넘으면 안되므로 만약 그럴 경우 sum을 0으로 만들어주었다.
  • 2231번 (분해합)

    const fs = require("fs");
    const input = +fs.readFileSync("./input.txt").toString().trim();
    let answer = 0;
    for (let i = input; i >= 0; i--) {
    if (i === 0 && answer === 0) {
    answer = 0;
    }
    const length = (i+"").length;
    let sum = i;
    for (let j = 0; j < length; j++) {
    sum += +(i+"")[j];
    }
    if (input === sum) {
    answer = i;
    }
    }
    console.log(answer);
  • 역시나 브루트 포스 알고리즘이라서 for문을 통해 input부터 0까지 내려가며 탐색하였다.
  • 만약 i 가 0이고 answer가 0이면 (생성자를 찾지 못했다는 뜻) answer를 0으로 하였다.
  • 분해합을 생성하는 과정은 sum에 원본숫자 i를 넣고 i를 string으로 변환하여 각 자리 숫자를 숫자형으로 만들어 더하는 것이다.
  • 만약 input과 sum이 같으면 answer에 i를 대입한다.
  • 7568번 (덩치)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    const N = +input.shift();
    let answer = new Array(5);
    for (let i = 0; i < input.length; i++) {
    input[i] = input[i].split(" ").map(Number);
    }
    for (let i = 0; i < N; i++) {
    let rank = 1;
    for (let j = 0; j < N; j++) {
    if (i !== j) {
    if (input[i][0] < input[j][0] && input[i][1] < input[j][1]) {
    rank++;
    }
    }
    }
    answer[i] = rank;
    }
    console.log(answer.join(" "));
  • 우선 인풋을 비교하기 편하게 이차원 배열 형태로 받아준다.
  • 첫번째 사람부터, 다른 모든 사람과 비교하여 자신보다 덩치가 큰 사람이 있는 경우 rank에 1을 더한다.
  • 이러한 방식으로 하면 문제 출력처럼 겹치는 랭크가 나올 수 있게 된다.
  • answer의 i번 인덱스에 rank를 넣어준다.
  • answer를 join을 이용해 문제 출력에 맞게 출력한다.
  • 1436번 (영화감독 숌)

    const fs = require("fs");
    const input = +fs.readFileSync("./input.txt").toString().trim();
    let num = 666;
    let i = 1;
    while (i !== input) {
    num++;
    if ((num + "").includes("666")) {
    i++;
    }
    }
    console.log(num);
  • num은 666, i는 1로 세팅한다.
  • num을 1씩 증가하며 666을 포함한 숫자가 있으면 i를 증가시킨다.
  • i가 input과 같아지면 멈추고 num을 출력한다.
  • 1018번 (체스판 다시 칠하기)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    const length = input.shift().split(" ").map(Number);
    let answer = 99999999;
    let num = 0;
    let blackBoardNum = 0;
    let whiteBoardNum = 0;
    const blackBoard = [
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"
    ];
    const whiteBoard = [
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
    ]
    for (let i = 0; i <= length[0]-8; i++) {
    for (let j = 0; j <= length[1]-8; j++) {
    checkPaintNum(i, j);
    }
    }
    function checkPaintNum(height, width) {
    blackBoardNum = 0;
    whiteBoardNum = 0;
    for (let i = 0; i < 8; i++) {
    for (let j = 0; j < 8; j++) {
    if (blackBoard[i][j] !== input[height+i][width+j]) {
    blackBoardNum++;
    }
    if (whiteBoard[i][j] !== input[height+i][width+j]) {
    whiteBoardNum++;
    }
    }
    }
    blackBoardNum > whiteBoardNum ? num = whiteBoardNum : num = blackBoardNum;
    if (num < answer) {
    answer = num;
    }
    }
    console.log(answer);
  • B로 시작하는 보드, W로 시작하는 보드를 배열로 준비했다.
  • 이 보드들과 비교하여 다른 요소가 있으면 숫자를 1 증가시키는 방법으로 칠할 인덱스의 개수를 구한다.
  • 두 숫자 중 더 작은 숫자를 num에 넣고 answer보다 num이 작으면 answer를 업데이트한다.
  • 이 과정을 한칸씩 옮기면서 수행한다.
  • answer를 출력한다.
  • 2309번 (일곱 난쟁이)

    const fs = require('fs');
    const input = fs
    .readFileSync('./input.txt')
    .toString()
    .trim()
    .split('\n')
    .map(Number);
    let sum = 0;
    let notDwarf = [];
    input.forEach((i) => {
    sum += i;
    });
    for (let i = 0; i < input.length; i++) {
    for (let j = 0; j < input.length; j++) {
    if (i !== j) {
    if (input[i] + input[j] === sum - 100) {
    notDwarf = [input[i], input[j]];
    break;
    }
    }
    }
    }
    let answer = input.filter((i) => i !== notDwarf[0] && i !== notDwarf[1]);
    answer = answer.sort((a, b) => a - b);
    console.log(answer.join('\n'));
  • 9명의 난쟁이들의 키의 합을 구하고 거기서 100을 빼줬다.
  • 2중 for문을 돌려서 두 난쟁이의 키의 합이 해당 값과 같은 것을 찾아냈다.
  • 이렇게 되면 찾아낸 두 난쟁이가 가짜 난쟁이이다.