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

문제 유형

• 누적합 알고리즘

문제 접근

• 답
  • 살아남은 건물 개수
• 주어지는 정보
  • Map 최대 크기 1,000,000(N*M)
  • 건물에 대한 명령 개수 최대 250,000(K)
• 후보
  • 완전 탐색
    • 불가능
    • 건물 1개마다 모든 명령을 적용하면 1,000,000*250,000으로 시간 초과
  • 누적합
    • 가능함
    • 모든 명령을 적용한 Command 배열을 만듦
    • 해당 배열을 최종 배열에 적용하면 시간 복잡도 N*M + K

코드

class Solution {
    int N,M;
    int[][] command;
    
    public void setCommand(int[][] board, int[][] skill){
        command = new int[N+1][M+1];
        
        for(int i = 0; i<skill.length; i++){
            int num = skill[i][0];
            int y = skill[i][1];
            int x = skill[i][2];
            int ny = skill[i][3];
            int nx = skill[i][4];
            int value = num == 1 ? -skill[i][5] : skill[i][5];
            
            command[y][x] += value;
            command[ny+1][x] += -value;
            
            command[y][nx+1] += -value;
            command[ny+1][nx+1] += value;
        }
        
        int sum = 0;
        for(int x = 0; x<M; x++){
            for(int y = 0; y<N; y++){
                sum += command[y][x];
                command[y][x] = sum;
            }
            sum = 0;
        }
        
        sum = 0;
        for(int y = 0; y<N; y++){
            for(int x = 0; x<M; x++){
                sum += command[y][x];
                command[y][x] = sum;
            }
            sum = 0;
        }
    }
    
    public void resolve(int[][] board){
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                board[i][j] += command[i][j];
            }
        }
    }
    
    public int countBuilding(int[][] board){
        int cnt = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                if(board[i][j] > 0){
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    public void printBoard(int[][] board){
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        N = board.length;
        M = board[0].length;
        
        setCommand(board, skill);
        resolve(board);
        
        //printBoard(board);
        
        answer = countBuilding(board);
        
        
        return answer;
    }
}

 

 

 

실패 코드

• 실패 이유
  • 누적합을 가로 방향으로만 생각함

  for(int j = y; j<=ny; j++){
      if(num==1){
          command[j][x] += -value;
          if(nx < M-1){
              command[j][nx+1] += value;
          }
          else if(j < N-1 && nx == M-1){
              command[j+1][0] += value;
          }
      }
      
      else if(num==2){
          command[j][x] += value;
          if(nx < M-1){
              command[j][nx+1] += -value;
          }
          else if(j < N-1 && nx == M-1){
              command[j+1][0] += -value;
          }
      }
  }

• 위 코드를 보면 각 명령때마다 각 행의 가로열에 누적합을 전부 만들고 있음
• 따라서, K * 1000(최대 행)의 연산이 발생하여 시간 초과

 

 

class Solution {
    int N,M;
    int[][] command;
    
    public void setCommand(int[][] board, int[][] skill){
        command = new int[N][M];
        
        for(int i = 0; i<skill.length; i++){
            int num = skill[i][0];
            int y = skill[i][1];
            int x = skill[i][2];
            int ny = skill[i][3];
            int nx = skill[i][4];
            int value = skill[i][5];
            
            for(int j = y; j<=ny; j++){
                if(num==1){
                    command[j][x] += -value;
                    if(nx < M-1){
                        command[j][nx+1] += value;
                    }
                    else if(j < N-1 && nx == M-1){
                        command[j+1][0] += value;
                    }
                }
                
                else if(num==2){
                    command[j][x] += value;
                    if(nx < M-1){
                        command[j][nx+1] += -value;
                    }
                    else if(j < N-1 && nx == M-1){
                        command[j+1][0] += -value;
                    }
                }
            }
            
            
        }
    }
    
    public void resolve(int[][] board){
        int sum = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                sum += command[i][j];
                board[i][j] += sum;
            }
        }
    }
    
    public int countBuilding(int[][] board){
        int cnt = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                if(board[i][j] > 0){
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    public void printBoard(int[][] board){
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        N = board.length;
        M = board[0].length;
        
        setCommand(board, skill);
        resolve(board);
        
        //printBoard(board);
        
        answer = countBuilding(board);
        
        
        return answer;
    }
}