[프로그래머스 Level.3] 파괴되지 않은 건물 (2022 KAKAO BLIND RECRUITMENT) (Java)
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/92344
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 파괴되지 않은 건물
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.
첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.
두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.
세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.
마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)
최종적으로 총 10개의 건물이 파괴되지 않았습니다.
건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.
제한사항
- 1 ≤ board의 행의 길이 (= N) ≤ 1,000
- 1 ≤ board의 열의 길이 (= M) ≤ 1,000
- 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
- 1 ≤ skill의 행의 길이 ≤ 250,000
- skill의 열의 길이 = 6
- skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
- type은 1 혹은 2입니다.
- type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
- type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
- (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
- 0 ≤ r1 ≤ r2 < board의 행의 길이
- 0 ≤ c1 ≤ c2 < board의 열의 길이
- 1 ≤ degree ≤ 500
- type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
- type이 2이면 degree만큼 건물의 내구도를 높입니다.
- type은 1 혹은 2입니다.
- 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.
정확성 테스트 케이스 제한 사항
- 1 ≤ board의 행의 길이 (= N) ≤ 100
- 1 ≤ board의 열의 길이 (= M) ≤ 100
- 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
- 1 ≤ skill의 행의 길이 ≤ 100
- 1 ≤ degree ≤ 100
효율성 테스트 케이스 제한 사항
- 주어진 조건 외 추가 제한사항 없습니다.
입출력 예
| board | skill | result |
| [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] | [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] | 10 |
| [[1,2,3],[4,5,6],[7,8,9]] | [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] | 6 |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
<초기 맵 상태>
첫 번째로 적이 맵의 (1,1)부터 (2,2)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.
두 번째로 적이 맵의 (0,0)부터 (1,1)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.
마지막으로 아군이 맵의 (2,0)부터 (2,0)까지 회복하여 100만큼 건물의 내구도를 높이면 아래와 같은 상황이 됩니다.
총, 6개의 건물이 파괴되지 않았습니다. 따라서 6을 return 해야 합니다.
제한시간 안내
- 정확성 테스트 : 10초
- 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
나의 코드
// 누적합의 변형 문제로 2차원 누적합 형태의 문제
class Solution {
public int solution(int[][] board, int[][] skill) {
int answer = 0;
int[][] newArr = new int[board.length + 1][board[0].length + 1];
for(int i=0; i<skill.length; i++) {
int y1 = skill[i][1];
int x1 = skill[i][2];
int y2 = skill[i][3] + 1;
int x2 = skill[i][4] + 1;
int num = skill[i][5];
if(skill[i][0] == 1) num *= -1;
newArr[y1][x1] += num;
newArr[y1][x2] -= num;
newArr[y2][x1] -= num;
newArr[y2][x2] += num;
}
// 누적합 계산 (상 -> 하)
for(int i=0; i<newArr[0].length; i++) {
for(int j=0; j<newArr.length-1; j++) {
newArr[j+1][i] += newArr[j][i];
}
}
// 누적합 계산 (좌 -> 우)
for(int i=0; i<newArr.length; i++) {
for(int j=0; j<newArr[0].length-1; j++) {
newArr[i][j+1] += newArr[i][j];
}
}
for(int i=0; i<board.length; i++) {
for(int j=0; j<board[0].length; j++) {
if(board[i][j] + newArr[i][j] > 0) answer++;
}
}
return answer;
}
}
// 브루트 포스 -> 모든 경우의 수를 탐색(시간복잡도가 O(N*M*K)으로 시간 초과 (K는 skill의 행 길이))
class Solution2 {
public int solution(int[][] board, int[][] skill) {
int answer = 0;
for(int i=0; i<skill.length; i++) {
if(skill[i][0] == 1) {
for(int j=skill[i][1]; j<=skill[i][3]; j++) {
for(int k=skill[i][2]; k<=skill[i][4]; k++) {
board[j][k] -= skill[i][5];
}
}
} else {
for(int j=skill[i][1]; j<=skill[i][3]; j++) {
for(int k=skill[i][2]; k<=skill[i][4]; k++) {
board[j][k] += skill[i][5];
}
}
}
}
for(int i=0; i<board.length; i++) {
for(int j=0; j<board[0].length; j++) {
if(board[i][j] > 0) answer++;
}
}
return answer;
}
}
풀이
- 브루트 포스로 문제를 풀면 정확성 테스트는 모두 성공하지만 효율성 테스트는 시간 복잡도 O(N*M*K )으로 모두 시간 초과로 실패한다.(K는 skill의 행 길이) 그래서 풀이 방법을 찾아보니 누적합을 이용해서 푸는 방법이 있었다.
- 누적합이란 누적한 값들을 계속 더해주는 방법인데 1차원 배열에서 보면 만약 [0, 0, 0, 0, 0, 0]의 배열에 인덱스 1부터 인덱스 3까지 2씩 더해주어 [0, 2, 2, 2, 0, 0]을 만들고 싶다면 for문을 이용하여 O(N)으로 풀 수 있지만 누적합을 이용해서 시작 부분인 1인덱스에 2를 넣고 3인덱스의 다음 인덱스인 4인덱스에 -2를 넣어주어 [0, 2, 0, 0, -2, 0]을 만든다. 그리고 마지막에 좌->우로 누적합을 해주면 [0, 2, 2, 2, 0, 0]이 되어 O(1)의 방식으로 풀 수 있는 것이다.
-
기존 누적합을 위한 방법 적용 좌에서 우로 누적합 [0, 0, 0, 0, 0, 0] [0, 2, 0, 0, -2, 0] [0, 2, 2, 2, 0, 0] - 이제 누적합을 변형하여 2차원 배열에서 적용시켜 보면 (0, 0) 부터 (2, 2)까지 사각형 형태에 2를 넣고 싶다면 다음과 같이 변형하여 상에서 하로 누적합을 한 번 진행하고 다시 좌에서 우로 누적합을 진행하면 skill을 먼저 적용한 후에 board를 돌면서 적용시키기 때문에 시간복잡도 O(N*M + K)으로 처리가 가능하다.
기존 누적합을 위한 방법 적용 상에서 하로 누적합 좌에서 우로 누적합 
- 주의 할 점은 만약 (0, 0)에서 (3, 3)까지 전부 2로 채우고 싶다면 -2를 넣을 다음 행과 다음 열이 없기 때문에 1행과 1열을 추가시켜줘야 한다. 따라서 위의 방법을 적용시키려면 1행 1열을 추가하여 적용시키고 마지막에 기존 board와 더해주면 된다.
- 이제 문제를 보면 누적합을 적용시키기 위해 board의 행과 열보다 1씩 큰 새로운 배열 newArr을 생성한다.
- skill을 for문을 돌면서 적용시킬 배열에서 직사각형의 네 꼭짓점의 점인 [y1][x1], [y1][x2], [y2][x1], [y2][x2]을 구하고 각 점에 skill[i][0]의 값에 따라 +값 또는 -값을 넣어주도록 한다. (적용시킬 다음 행에 y2와 x2는 값을 넣어줘야 하므로 +1씩 해주도록 한다)
- 그 후에 newArr을 돌면서 각 열의 상에서 하로 누적합을 진행하고 다시 한 번 newArr을 돌면서 각 행의 좌에서 우로 누적합을 진행한다.
- 이제 0으로 모두 초기화 된 newArr 배열에 skill을 모두 적용시켰으니 기존 배열인 board와 더해주면 된다.
- board의 값과 newArr의 값을 더해 0보다 크다면 파괴되지 않은 건물이므로 answer를 증가시키고 최종적으로 answer를 반환하면 된다.