[백준] 0917 오늘의 문제 풀이📚

오늘은 달랑 두 문제 풀었다. 아직도 게으름을 벗지 못했다니..

1. 체스판 다시 칠하기

2. 영화감독 숌

 

1. 체스판 다시 칠하기

a. 처음 풀이

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const firstline = input.shift().split(' ');
    const height = Number(firstline[0]);
    const width = Number(firstline[1]);
    const color = ['B', 'W'];

    let counts = [];
    let count, count_2;

    for(let i = 0; i < height - 7; i++) {
        for(let j = 0; j < width - 7; j++) {
            count = 0;
            count_2 = 0;
            const criteria = input[i][j];
            const criteria2 = color.find(el => el != input[i][j]);

            for(let m = 0; m < 8; m++) {
                for(let n = 0; n < 8; n++) {
                    if(m % 2 === 0) {
                        if(n % 2 === 0) {
                            if(input[i + m][j + n] !== criteria) {
                                count++;
                            } 
                            if(input[i + m][j + n] !== criteria2) {
                                count_2++;
                            } 
                        } else if(n % 2 === 1) {
                            if(input[i + m][j + n] === criteria) {
                                count++;
                            }
                            if(input[i + m][j + n] === criteria2) {
                                count_2++;
                            } 
                        }
                    } else if(m % 2 === 1) {
                        if(n % 2 === 0) {
                            if(input[i + m][j + n] === criteria) {
                                count++;
                            }
                            if(input[i + m][j + n] === criteria2) {
                                count_2++;
                            } 
                        } else if(n % 2 === 1) {
                            if(input[i + m][j + n] !== criteria) {
                                count++;
                            }
                            if(input[i + m][j + n] !== criteria2) {
                                count_2++;
                            } 
                        }
                    }
                }   
            }

            counts.push(count);
            counts.push(count_2);
        }
    }
    counts.sort((a, b) => a - b);
    console.log(counts[0]);
});

브루트 포스라고 너무 막무가내로 풀었나 ㅋㅋ..

사실 for문을 네 개나 쓴다는 게 너무 말도 안된다고 생각해서 엄청 오래 고민했던 문제.

결국 for문을 네 개 써봤는데, 시간초과가 안되더라?

아마 안쪽의 두 개 for문은 범위가 0~8까지로 정해져있어서 그런듯.

근데 메모리도 많이 잡아먹고 시간도 좀 오래 걸리는 것 같다.

 

b. 참고해서 다시 풀기

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const firstline = input.shift().split(' ');
    const height = Number(firstline[0]);
    const width = Number(firstline[1]);

    let min = Infinity;
    let count = 0, count_2 = 0;

    for(let i = 0; i < height - 7; i++) {
        for(let j = 0; j < width - 7; j++) {
            count = 0;
            count_2 = 0;

            for(let m = 0; m < 8; m++) {
                for(let n = 0; n < 8; n++) {
                    if((m + n) % 2 === 0) {
                        // 0, 2, 4, 6, 8...
                        if(input[i + m][j + n] === 'B') {
                            // 짝수가 'W'여야 하는 경우
                            count++;
                        } else {
                            // 짝수가 'B'여야 하는 경우
                            count_2++;
                        }
                    } else {
                        // 1, 3, 5, 7, 9...
                        if(input[i + m][j + n] === 'W') {
                            // 홀수가 'B'여야 하는 경우 = 짝수가 'W'여야 하는 경우
                            count++;
                        } else {
                            count_2++;
                        }
                    }
                }
            }
            
            min = min > count ? count : min;
            min = min > count_2 ? count_2 : min;
        }
    }

    console.log(min);
});

구글링을 해보니, 어떤 분이 대각선 단위로 움직이면서 풀었더라..

나는 (i, j)로 한 칸 한 칸 다 검사하면서 풀었는데

생각해보니 i + j로 접근하면

0 1 2 3 4 5 6

1 2 3 4 5 6 7 

2 3 4 5 6 7 8

이런 식이라서, 대각선 단위로 홀, 짝을 나누어 풀 수가 있었다.

덕분에 if문이 하나 줄었다.

 

메모리도 거의 절반 정도만 썼고, 시간도 한 50ms정도 단축한 듯.

계속 문제를 풀다보면 나도 이런 풀이를 아무렇지 않게 슥슥 쓸 수 있게 되려나..

 

2. 영화감독 숌

a. 처음 풀이

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const number = Number(input[0]);
    let i = 0;
    let count = 0;
    
    while(count < number) {
        i++;
        if(String(i).includes('666')) {
            count++;
        }
    }
    console.log(i);
});

별다른 어려움 없이 풀어서 그냥 넘어가려고 했는데

웬걸, 메모리를 71884KB나 잡아먹는 풀이였다. 

아마 String을 계속해서 생성해내기 때문에 그런 듯.

시간도 그렇게 빠른 것도 아니고..

 

그래서, 숫자로 풀어보려고 노력했는데

엄청 오랫동안 고민하다가 결국 구글링..

 

b. 참고해서 다시 풀기

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const number = Number(input[0]);
    let i = 665;
    let count = 0;

    while(count < number) {
        i++;
        let temp = i;
        while(temp) {
            if(temp % 1000 === 666) {
                count++;
                break;
            }
            temp = (temp / 10) >> 0;
        }
    }
    console.log(i);
});

왜 이 생각을 못했지..

temp에 숫자가 들어가는데, while문의 조건으로 temp를 그냥 넣어버리면

temp를 10으로 나눈 결과가 0이 되면 while문을 벗어나게 된다.

0이 false값인 건 이미 알고 있는 사실인데, 이런 때에 불쑥 적용하려면 못하겠다.

 

숫자에 '666'이 포함되어있는지 나눗셈으로 확인하기 위해서는

1의 자리에서부터 시작해서 한 자리씩 올라가면서 1000으로 나눠주면서 나머지를 확인하면 된다.

temp = (temp / 10) >> 0의 뒤쪽의 비트 연산자는 정수로 만들어주기 위해서.

 

정수로 만들어주는 건 비트 연산자가 가장 빠르다고 하니, 애용해야겠다.

 

엄청 쉬운 문제인 줄 알았지만, 생각보다 배운 점이 많았던 문제.