[JS 백준] 1780.종이의 개수

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

기본적인 분할 정복 문제다.

 

처음에 모든 종이내부의 숫자가 일치하지 않으면 9등분으로 나누고

 

나눈 것에서도 전부 일치하지않으면 9등분을 해서 정답을 찾아나가는 방식이다.

 

처음 시간 초과가 발생한 이유는 Flag배열을 사용해 검색했는지 안했는지 체크를 하고 다음 부분을 검색해 나가려했는데.

 

이분 탐색문제는 index와 재귀를 활용해 풀어야 시간초과가 나지 않고 제대로 풀 수 있었다.

 

그리고 Number 또는 parseInt를 통해 자료형을 변경해 풀이를 진행하면

 

변환시간때문애 시간초과가 나기에 문자열을 그대로 받아서 사용했다.

 

하.. 또 문자열로 받으니까 입력값에 마지막 '\r'이 들어가 replace('\r' ,'').split(' '); 을 통해 배열을 바로 받아 사용했다.

 

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';

let [N,...paper] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim().split('\n');

 N = +N;

let result = new Array(3).fill(0); // 결과값을 담을 배열
paper = paper.map(s => s.replace('\r', '').split(' '));

// 분할 정복 함수
const divideConquer = (column, row, length) => {
    if(checkBox(column, row, length)){
        const num = paper[column][row];
        if(num === '-1'){
            result[0]++;
        }else if(num === '0'){
            result[1]++;
        }else{
            result[2]++;
        }
        
    }else{
        let newLength = length/3;
        for(let i = 0; i < 3; i++){
            for(let j = 0; j < 3; j++){
                divideConquer(column+ newLength * i , row + newLength*j, newLength);
            }
        }
    }

}

// 체크 함수
const checkBox = (column, row, length) => {

    let firstnum = paper[column][row];

    for(let i = 0; i < length; i++){
        for(let j = 0; j < length; j++){
            if(paper[column+i][row+j] !== firstnum){
                return false;
            }
        }
    }
    
    return true;
}

divideConquer(0,0,N);

let String = `${result[0]+'\n'+result[1]+'\n'+result[2]}`
console.log(String);

 

주의할 점

let [N,...paper] = require("fs")

const 로 받아서 사용하면 paper 배열을 바로 사용할 수 없다.

 

이분탐색을 한문제 더 풀어봐야겠다.