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

# 문제 원문

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

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

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 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

제한시간 안내

• 정확성 테스트 : 10초
• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

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

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

 

# 문제 풀이

 

저번 테스트에서 정확성을 브루트포스로 풀고 효율성을 못 푼 문제이다. 개인적으로 2차원 배열에 누적합을 적용하는 방법을 몰랐기에 풀이을 전혀 진행하지 못했다. 물론 skill의 결과를 모두 모아서 처리 할 생각은 했지만 누적합 관련해서 공식에 대한 지식이 없기에 r1,c1 과 r1 c2 등에 degree를 +하거나 - 하는 방식으로 풀어가는 정도 생각을 떠올린 정도 1차원 배열 누적합과 2차원 배열 누적합에 대한 카카오 블로그 해설을 듣고 나서야 간신히 풀었다. 누적합이라는 것에 대한 이해가 해당 문제의 난이도를 좌지우지한다. 실제로 테스트 참가자 51퍼센트가 통과한 정확성과 다르게 효율성의 경우 2프로 대의 정답률을 보인다. 그리고 보니 이게 어떻게 3레벨 문제일까?4레벨 가까운 3레벨일려나..? 다음에 비슷한 문제를 만나면 쉽게 풀 수 있기를..

• 정답률 : 정확성 51.11%, 효율성 1.86%

 

# 솔루션 플로우

1. 입력 받은 board의 row와 col 길이에서 1을 더한 prefixSum 2차원 배열을 선언한다.

2. 입력 받은 skill을 순회하면서 각 데이터에 맞는 포인트(4포인트)에 degress값을 prefixSum에 합해준다.

3. 구해진 누적합을 row와 col 순차적으로 모든 요소의 누적합을 구해준다.

4. 구해진 누적합prefixSum의 각 요소를 입력 받은 board 요소에 대입해서 계산해준다.

5. 모든 계산이 끝난 board에서 0이상의 요소의 갯수합 result를 구한다.

6. 얻은 result를 반환한다.

1. 누적합

function solution(board, skill) {
    const prefixSum = Array.from(
        { length: board.length + 1 },
        (_) => new Array(board[0].length + 1).fill(0)
    );

    skill.forEach((el) => {
        const [type, r1, c1, r2, c2, degree] = el;
        const sum = type === 1 ?
            -degree :
            degree;
        prefixSum[r1][c1] += sum;
        prefixSum[r2 + 1][c2 + 1] += sum;
        prefixSum[r1][c2 + 1] -= sum;
        prefixSum[r2 + 1][c1] -= sum;
    });

    for (let r = 0; r < prefixSum.length; r++) {
        for (let c = 1; c < prefixSum[0].length; c++) {
            prefixSum[r][c] += prefixSum[r][c - 1];
        }
    }
    for (let r = 1; r < prefixSum.length; r++) {
        for (let c = 0; c < prefixSum[0].length; c++) {
            prefixSum[r][c] += prefixSum[r - 1][c];
        }
    }
    prefixSum.forEach((row, rdx) => {
        row.forEach((col, cdx) => {
            if (board[rdx] && board[rdx][cdx]) {
                board[rdx][cdx] += col;
            }
        });
    });


    return board.reduce((result, row) =>
        result + row.reduce((result, current) =>
            current > 0 ?
                result + 1 :
                result
            , 0)
        , 0);
}