[프로그래머스][이분탐색] 선인장 숨기기

     

목차

 

 

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/468379

프로그래머스

 

 

문제 구현 방법

다음과 같이 이차원 배열에 대한 누적합을 구하는 것을 알아 두면 이 문제에서 4중 반복문을 안돌리고 풀 수 있다.

// 1. 원본 격자 데이터 (3 x 3)
const board = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

const m = 3; // 행 개수
const n = 3; // 열 개수

// 2. 누적 합 배열 초기화 (4 x 4 크기를 0으로 채움)
const prefix = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

// 3. 2차원 누적 합 채우기
for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
        let temp = board[i][j]; // 현재 칸의 값
        
        // [핵심 공식]
        // 현재 칸의 값 + 왼쪽 누적합 + 위쪽 누적합 - 대각선 왼쪽 위 누적합
        prefix[i + 1][j + 1] = temp + prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j];
    }
}

// 4. 결과 출력
console.log("--- 완성된 prefix 배열 ---");
console.table(prefix);

 

(index)	0	1	2	3
0	0	0	0	0
1	0	1	3	6
2	0	5	12	21
3	0	12	27	45

 

여기서 내가 원하는 칸만큼의 누적합을 구하면 코드는 다음과 같다.

let sum = prefix[i + h][j + w] - prefix[i][j + w] - prefix[i + h][j] + prefix[i][j];

 

 

또한 이 문제는 50만을 순회해야 하기때문에 50만 x 50만은 시간 초과로 이분탐색을 통해 효율적으로 풀 수 있다.

 

 

코드 구현

function solution(m, n, h, w, drops) {

    var answer = [0, 0]; 
    
    let board = Array.from({length: m}, () => Array(n).fill(0));

    drops.forEach((drop, idx) => {
        let [r, c] = drop;
        board[r][c] = idx + 1;
    });
    let startDay = 1;
    let endDay = drops.length;

    while(startDay <= endDay){
        let midDay = Math.floor((startDay+endDay)/2);
        
        let temp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
        
         for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                let pls = (board[i][j] <= midDay && board[i][j] > 0) ? 1 : 0;
                temp[i + 1][j + 1] = pls + temp[i + 1][j] + temp[i][j + 1] - temp[i][j];
            }
        }
        
        let foundSafeZone = false;
        let currentDayBest = null;

        for (let i = 0; i <= m - h; i++) {
            for (let j = 0; j <= n - w; j++) {
                let sum = temp[i + h][j + w] - temp[i][j + w] - temp[i + h][j] + temp[i][j];
                
                if (sum === 0) {

                    currentDayBest = [i, j];
                    foundSafeZone = true;
                    break; 
                }
            }
            if (foundSafeZone) break; 
        }
        if(foundSafeZone){
            startDay = midDay +1;
            answer = currentDayBest;
        }else{
            endDay = midDay -1;
        }
        
    }

    return answer;
}