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

프로그래머스 Level 3 - 파괴되지 않은 건물

• 문제 분류 : 2022 카카오 블라인드 채용
• 문제 출처 : 프로그래머스 Level 3 - 파괴되지 않은 건물

📌 문제 설명

📌 생각한 풀이 방법 (1차 시도 -> 효율성 실패)

1. 조건에 맞게 그대로 구현한다.

📌 풀이

function solution(board, skill) {
  let answer = 0;

  for (let i = 0; i < skill.length; i++) {
    let current = skill[i];
    let attack = current[0] === 1 ? true : false;
    let value = current[5];
    for (let j = current[1]; j <= current[3]; j++) {
      for (let k = current[2]; k <= current[4]; k++) {
        if (attack) {
          board[j][k] -= value;
        } else {
          board[j][k] += value;
        }
      }
    }
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] > 0) {
        answer++;
      }
    }
  }

  return answer;
}

📌 생각한 풀이 방법 (2차 시도 -> 성공)

1. 밑과 옆으로 board보다 1을 증가시킨 배열을 생성한다.
2. skill에 맞게 해당 좌표에 만족하는 값 중 arr (x1, y1)과 (x2+1,y2+1)에 해당 값을 조건에 만족하는 값을 더한다.
3. arr의 (x2+1,y1), (x1,y2+1)에 만족하는 부분을 attack * -1 만큼 더한다.
4. 모든 skill을 탐색한 후, 해당 값을 누적하여 위에서 아래로 더한다.
5. 위에서 아래로 더한 후, 해당 값을 누적하여 왼쪽에서 오른쪽으로 더한다.
6. board에 해당 배열인 arr을 더해 최종 배열을 구한다.
7. 해당 값 중 0보다 큰 위치의 수를 더해 answer을 반환한다.

📌 풀이

function solution(board, skill) {
  let answer = 0;
  let arr = Array.from({ length: board.length + 1 }, () =>
    Array(board[0].length + 1).fill(0)
  ); // 밑과 옆으로 board보다 1을 증가시킨 배열을 생성

  for (let i = 0; i < skill.length; i++) {
    let current = skill[i];
    let attack = current[0] === 1 ? -1 : 1;
    arr[current[1]][current[2]] += current[5] * attack; // (x1, y1)
    arr[current[3] + 1][current[2]] += current[5] * attack * -1; // (x2+1,y1)
    arr[current[1]][current[4] + 1] += current[5] * attack * -1; // (x1,y2+1)
    arr[current[3] + 1][current[4] + 1] += current[5] * attack; // (x2+1,y2+1)
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      arr[i + 1][j] += arr[i][j]; // 해당 값을 누적하여 위에서 아래로 더한다
    }
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      arr[i][j + 1] += arr[i][j]; // 해당 값을 누적하여 왼쪽에서 오른쪽으로 더한다
    }
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      board[i][j] += arr[i][j]; // board에 해당 배열인 arr을 더해 최종 배열
    }
  }

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j] > 0) {
        answer++; // 해당 값 중 0보다 큰 위치의 수
      }
    }
  }

  return answer;
}