2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물 (JAVA)

❓ 문제 - 2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 - JAVA 풀이법

출처 

(https://programmers.co.kr/learn/courses/30/lessons/92344)

코딩테스트 연습 - 파괴되지 않은 건물

 

📝 문제해결법 1 (정확성만 맞는 풀이 )

1. 간단한 브루트 포스를 활용해서 문제를 해결하였다.

1 ≤ board의 행의 길이 (= N) ≤ 100 1 ≤ board의 열의 길이 (= M) ≤ 100 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100 1 ≤ skill의 행의 길이 ≤ 100 1 ≤ degree ≤ 100

• 정확성 테스트 케이스 제한 사항이 다음과 같기 때문에 브루트 포스로만 해결해도 간단하게 통과는 가능하다.
• 간단하게 for문을 활용해서 문제에 주어진 조건 그대로 구현하면 시간복잡도가 O(N*M*K(skil의 행 길이))가 되기 때문이다.

 

💻 소스코드 1

import java.util.*;

class Solution {
    
    public static int[][] boards;
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        boards = board;
        
        
        for(int[] s:skill){
            do_skill(s);
        }
        
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                if(boards[i][j] > 0) answer++;
            }
        }
        
        return answer;
    }
    
    public static void do_skill(int[] s){
        int r1 = s[1];
        int c1 = s[2];
        int r2 = s[3];
        int c2 = s[4];
        int degree = s[5];
        if(s[0] == 1){
            for(int i=r1;i<=r2;i++){
                for(int j=c1;j<=c2;j++){
                    boards[i][j] -= degree;
                }
            }
        } else {
            for(int i=r1;i<=r2;i++){
                for(int j=c1;j<=c2;j++){
                    boards[i][j] += degree;
                }
            }
        }
    }
}

 

😎 실행결과1

 

📝 문제해결법 2 ( 정확성과 효율성 두 마리 토끼를 잡는 풀이)

1. 누적합을 통해 해결한다면 효율성의 두 마리 토끼를 잡을 수 있다.

 

1) 우선 해설 풀이를 기반으로 코드를 작성했다.

• 카카오 해설 풀이(https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/)

* 누적합에 대한 접근 방법 공부

(1) 1차원 누적합

• 문제에서 만약 주어진 degree가 2라면 a 구간에서 b구간까지의 degree를 빼주기 위해서는 for문을 활용하는 방법은 O(M)의 시간복잡도가 걸리지만,  누적합을 사용한다면 O(1)의 시간복잡도로 처리가 가능해진다.
• 만약 [1, 2, 3, 4, 5] 에서 0번인덱스부터 3번 인덱스까지 2를 더해주고 싶다면 [2, 0, 0, 0, -2] 라는 새로운 배열을 생성한 뒤에 이 새로운 배열을 0번인덱스 -> 마지막 인덱스까지 누적합 시키면 [2, 2, 2, 2, 0] 이라는 배열이 생성된다. 이 누적합된 배열과 기존의 [1, 2, 3, 4, 5] 배열을 더해주면 [3, 4, 5, 6, 7, 5] 라는 구하려고 하는 배열의 형태가 될 수 있다.
• 즉, 누적합을 통해 원하는 배열을 만들기 위해 1차원 배열에서 변화시키려는 구간이 a ~ b 구간이고 c의 변화를 주려면 새로운 배열에 a 번째 원소에 c를 더하고, b+1 번째 원소에 -c를 빼준 후 누적합 시키면 된다.

 

하지만 문제에서 주어진 것은 2차원 형태이고, 1차원 배열로만 누적합을 이용해서 구현한다면 O(N*M*K)의 시간복잡도를 O(N*K)로 줄일 수 있지만, 시간 초과가 발생한다. 따라서 2차원 배열의 누적합을 변화시키는 경우를 다시 생각해보아야 한다.

 

 

(2) 2차원 누적합

1. 1차원 누적합의 형태로 행만큼 만드는 경우 ( 각 행에 변화를 적용) n 0 0 -n n 0 0 -n n 0 0 -n

2. 2차원 누적합의 형태의 아이디어 ( 각 열에도 변화를 적용) n 0 0 -n 0 0 0 0 0 0 0 0 -n 0 0 n

 

• 1번은 위에서 설명한 1차원의 누적합 형태를 각 행마다 적용시킨 것이다. 이 형태를 열 단위로 살펴보면 이것도 열의 형태로 누적합된 상태 이므로 각 열에서 위의 누적합 아이디어를 적용시키면 된다.
• 따라서 2의 형태로 (r1, c1) ~ (r2, c2)에 n만큼의 변화를 주고 싶다면 (r1, c1)에 n을 더하고, (r2+1, c1)에 n을 빼고, (r1, c2+1)에 n을 빼고 (r2+1, c2+1)에 n을 더한 새로운 배열의 형태를 만들어 준 뒤에 위 -> 아래 만큼 누적합, 왼쪽 -> 오른쪽으로 누적합의 두 번을 해주면 원하는 변화시켜주려는 2차원 배열의 형태가 된다.

2) 문제의 적용

• 새로운 배열 sums에 skill에 대한 모든 처리를 해준 후, 기존 배열 board에 반영 해줘야 하기 때문에 시간 복잡도가 O(N*M + K)로 처리가 가능해진다.
• 위의 아이디어를 기반으로 type에 따라 degree만큼 더해주거나, 빼는 부호만 잘 조절해서 새로운 배열 sums에 처리를 해준 값을 저장한다.
• 모든 skill에 대한 처리를 sums라는 배열에 반영한 뒤, 위 -> 아래로 누적합 처리 그리고 왼쪽 -> 오른쪽으로 누적합 처리를 진행해준다.
• 처리 후 sums라는 배열과 boards에 값을 더해줘서 만약 boards[i][j]가 0보다 크다면 파괴되지 않은 건물이므로 answer에 1을 더해준다.

3) 주의할 점과 느낀점

• 배열 범위 조심 : 새로운 배열 sums에서 위 아이디어를 적용시키려면 기존에 board 배열의 행과 열 크기에 1씩 더 크게 잡아줘야 위 아이디어를 처리가 가능해진다.
• 사실 정확도로 해결하는 것은 바로 브루트포스를 생각했지만 효율성을 어떤 알고리즘을 적용시켜서 해결해야할지 고민이 컸다. 대략 1시간 넘게 고민했지만 내가 알고있는 알고리즘으로 풀이가 가능할 것 같지 않아 해설을 살짝 훑은 후,, 너무 감탄했다.. 이런 새로운 풀이, 해설로 알고리즘 접근하는 거 넘 재밌다...

 

 

💻 소스코드 2

import java.util.*;

class Solution {
    
    public static int[][] sums;
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int r = board.length;
        int c = board[0].length;
        sums = new int[r+1][c+1];
        
        for(int[] s:skill){
            int type = s[0];
            if(type == 1){
                sums[s[1]][s[2]] -= s[5];
                sums[s[3]+1][s[2]] += s[5];
                sums[s[1]][s[4]+1] += s[5];
                sums[s[3]+1][s[4]+1] -= s[5];
            } else {
                sums[s[1]][s[2]] += s[5];
                sums[s[3]+1][s[2]] -= s[5];
                sums[s[1]][s[4]+1] -= s[5];
                sums[s[3]+1][s[4]+1] += s[5];
            }
        }
        

        // 위 -> 아래
        for(int j=0;j<c+1;j++){
            for(int i=0;i<r;i++){
                sums[i+1][j] += sums[i][j];
            }
        }
        

        // 왼 -> 오른
        for(int i=0;i<r+1;i++){
            for(int j=0;j<c;j++){
                sums[i][j+1] += sums[i][j];
            }
        }
        
        
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(board[i][j] + sums[i][j] > 0) answer++;
            }
        }
        
        return answer;
    }
    

}

😎 실행결과2