[프로그래머스 92344] 파괴되지 않은 건물

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

프로그래머스

 

 

위의 문제에서 완전 탐색을 수행하면 무 조 건 효율성에서 시간초과가 뜬다..

효율성을 통과할 방식을 고민해 보았으나 영 방법이 떠오르질 않아서 😅 질문 게시글을 읽었다..

 

처음에 내가 생각한 방식은 아래 글

다음과 같은 테스트 케이스를 예시로 들면

board = 

1	2	3
4	5	6
7	8	9

skill = {

1번째 스킬 : {1, 1, 1, 2, 2, 4},

2번째 스킬 : {1, 0, 0, 1, 1, 2},

3번째 스킬 : {2, 2, 0, 2, 0, 100},

4번째 스킬 : {1, 0, 1, 1, 2, 3}

}

 

1 . 다음 표와 같이 각 스킬에 대한 누적 value를 구한다.

 

[0 ~ 0] 0

[0 ~ 1] -4

[0 ~ 2] -6

[0 ~ 3] 94

[0 ~ 4] 91

 

2. board의 각 위치에 적용되는 스킬 구간을 통하여 부분 누적 value를 계산한다.

ex ) 

(r, c) = (1, 1) 위치에 적용되는 스킬은 1, 2, 4 번째 스킬이므로 해당 위치의 부분 누적 value는

= [0~2] + [4~4]

= [0~2] + [0~4] - [0~3]

= -9 이다.

 

 

 👉👉 

이와 같은 방식의 문제점은.. "구간"을 처리하는 게 어렵다는 점이다.

각 위치에 따른 구간을 계산해야 하므로 이의 시간복잡도는 O(N*M *O(구간처리)) 이라고 할 수 있다.

근데 이 때의 구간처리 시간복잡도에 대해 O(skill)보다 효율적인 방식을 떠올리지 못하겠다는 게 문제다..

 

 

공식 풀이

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

위의 풀이에서는 skill이 적용되는 범위에 누적되는 degree 계산을 구간 합을 이용하여 풀이하였고,

구간 합을 구하는 방식을 1차원에서 2차원으로 넓혀서 설명하고 있다.

1차원에서의 구간 합 계산 방식은 다음과 같이 두고 풀이할 수 있다.

 

i= 2에서부터 j=5까지의 구간에 2를 더해야 할 때.

0

0

2

0

0

0

-2

 

배열의 초기값을 위와 같이 설정하고, 이 배열에 누적 합을 적용하면 원하는 구간 2 ~5 에 대해 값을 더할 수 있다.

0

0

2

2

2

2

0

 

이러한 활용을 이차원 배열에 적용해 보면 다음과 같다.

(2, 2) 부터 (3, 3) 까지의 범위에 대해 3을 더해야 할 때

0	0	0	0	0
0	0	0	0	0
0	0	3	0	-3
0	0	0	0	0
0	0	-3	0	3

 

배열의 초기값을 위와 같이 설정하고 가로 방향(👉)에 대해 누적 합을 계산하고, 세로 방향(👇)에 대해 누적 합을 계산하면 다음과 같이 계산된다.

0	0	0	0	0
0	0	0	0	0
0	0	3	3	0
0	0	3	3	0
0	0	0	0	0

 

 

이러한 방식을 이용하여, 각 스킬마다 해당되는 위치에 초기 값을 세팅하고, 누적 합을 계산하여 해당 위치의 최종 value를 통하여 결과값을 구할 수 있다. ㅜㅜ

 

 

 

class Solution {

   int N, M;
   long[][] sum;

   public int solution(int[][] board, int[][] skill) {
      N = board.length;
      M = board[0].length;
      sum = new long[N + 1][M + 1];
      init(skill);

      return calBoard(board);
   }

   private void init(int[][] skill) {
      for (int i = 0; i < skill.length; i++) {
         int r1 = skill[i][1], c1 = skill[i][2];
         int r2 = skill[i][3], c2 = skill[i][4];
         int degree = (skill[i][0] == 1) ? -skill[i][5] : skill[i][5];

         sum[r1][c1] += degree;
         sum[r2 + 1][c2 + 1] += degree;

         sum[r1][c2 + 1] -= degree;
         sum[r2 + 1][c1] -= degree;
      }
   }

   private int calBoard(int[][] board) {

      for (int r = 0; r < N; r++) {
         long total = 0;
         for (int c = 0; c < M; c++) {
            total += sum[r][c];
            sum[r][c] = total;
         }
      }

      int cnt = 0;
      for (int c = 0; c < M; c++) {
         long total = 0;
         for (int r = 0; r < N; r++) {
            total += sum[r][c];
            sum[r][c] = total + board[r][c];
            if (sum[r][c] > 0) {
               cnt++;
            }
         }
      }
      return cnt;
   }
}