프로그래머스 LV3 - 파괴되지 않은 건물

문제를 처음 보는 순간,

skills의 범위가 1<= skills <= 250000 이라는 것이 문제의 핵심이라는 걸 알았다.

분명 단순한 반복문으로 해결하면 반드시 타임아웃에 걸릴게 확실하다. (물론 그러니까 3단계 문제인 것이겠지만은)

문제는 어떻게 이 범위데미지를 각 노드를 모두 순회하지 않고 전체에 주냐는 것이다.

하지만 일단은 생각은 잠시 미뤄두고 무작정 풀어봤다.

 

import java.util.*;

class Solution {
    private Map<String,Integer> damageCountMap = new HashMap<>();
    
    public int solution(int[][] board, int[][] skill) {
        for (int[] arr : skill) {
            int type = arr[0];
            int startY = arr[1];
            int startX = arr[2];
            int endY = arr[3];
            int endX = arr[4];
            int degree = type==1?arr[5] * -1 : arr[5];
            
            for (int x = startX; x <= endX; x++) {
                for (int y = startY; y <= endY; y++) {
                    String target = getKey(x, y); 
                    Integer currentDegree = damageCountMap.computeIfAbsent(target, k -> 0);
                    damageCountMap.put(target, currentDegree + degree);
                }
            }
        }

        int answer = 0;

        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length; x++) {
                int currentDegree = board[y][x];
                String target = getKey(x, y);
                if(damageCountMap.containsKey(target)){
                    currentDegree += damageCountMap.get(target);
                }

                if(currentDegree > 0){
                    answer ++;
                }
            }
        }
        
        return answer;
    }
    
    private String getKey(int x, int y){
        return  x + " " + y;
    }
}

 

역시 모든 테스트항목에서 타임아웃이 발생했다 ㅋㅋ 참나

그래서 최대한 skills의 반복을 피하는 방법을 생각해본다.

board의 가로세로 최대값은 100이기 때문에 웬만한 반복은 문제없기 때문에,

모서리값들을 df 변수에 저장하고 df 를 순회하며 계산하도록 한다. 

 

class Solution {

    public int solution(int[][] board, int[][] skill) {
        //누적합 계산할 배열.
        int[][] df = new int[board.length + 1][ board[0].length + 1];

        for (int[] arr : skill) {
            int type = arr[0];
            int startY = arr[1];
            int startX = arr[2];
            int endY = arr[3];
            int endX = arr[4];
            int degree = type==1?arr[5] * -1 : arr[5];

            df[startY][startX] += degree;
            df[endY + 1][startX] -= degree;
            df[startY][endX + 1] -= degree;
            df[endY + 1][endX +1] += degree;

        }

        //df x값 채우기
        for(int y = 0; y < board.length; y++){
            for (int x = 1; x < board[0].length; x++) {
                df[y][x] += df[y][x-1];
            }
        }

        //y값 채우기.
        for(int y = 1; y < board.length; y++){
            for (int x = 0; x < board[0].length; x++) {
                df[y][x] += df[y-1][x] ;
            }
        }

        int answer = 0;

        //board와 df 합산하여 값 도출
        for(int y = 0; y < board.length; y++){
            for (int x = 0; x < board[0].length; x++) {
                if(board[y][x] + df[y][x] > 0){
                    answer ++;
                }
            }
        }

        return answer;
    }

}

 

성공 대성공.

처음 df[endY + 1][endX +] += degree; 부분을 누락했는데,

x값을 채우는 부분과 y값 채우는부분에서 중첩되어 두배로 - 되는 문제가 있었다.

그래서 degree 값을 한번 더해주도록 하여 해결했다.