프로그래머스 LEVEL 3(파괴되지 않은 건물)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-05-05

  • 해결 방법 :

    • 누적합을 통해 문제 해결
      • skill을 돌며 공격, 회복에 대한 누적합 저장
      • 우측으로 누적합, 아래측으로 누적합 계산
      • board와 누적합 계산

  • 회고 :

    • 처음 작성한 코드

      function solution(board, skill) {
  skill.forEach(([type, r1, c1, r2, c2, degree]) => {
    const sign = type === 1 ? -1 : 1;
    for (let x = c1; x <= c2; x++) {
      for (let y = r1; y <= r2; y++) {
        board[y][x] += sign * degree;
      }
    }
  });

  return board.flat().filter((v) => v >= 1).length;
}

    • 당연하게도 효율성 테스트에서 전부 시간 초과가 발생했다..

      image

    • 곰곰이 생각한 결과 누적합을 통해 문제를 해결할 수 있다 생각하여 아래와 같이 작성하였다.

      function solution(board, skill) {
  const maxX = board[0].length,
    maxY = board.length;

  const prefixSum = Array.from({ length: maxY + 1 }, () =>
    Array.from({ length: maxX + 1 }, () => 0),
  );

  skill.forEach(([type, r1, c1, r2, c2, degree]) => {
    const d = type === 1 ? -1 * degree : degree;

    prefixSum[r1][c1] += d;
    prefixSum[r2 + 1][c2 + 1] += d;
    prefixSum[r1][c2 + 1] -= d;
    prefixSum[r2 + 1][c1] -= d;
  });

  for (let y = 0; y <= maxY; y++) {
    for (let x = 1; x <= maxX; x++) {
      prefixSum[y][x] += prefixSum[y][x - 1];
    }
  }

  for (let x = 0; x <= maxX; x++) {
    for (let y = 1; y <= maxY; y++) {
      prefixSum[y][x] += prefixSum[y - 1][x];
    }
  }

  return board.map((rows, i) => rows.filter((v, j) => v + prefixSum[i][j] >= 1)).flat().length;
}

      image

    • 그 결과 효율성 테스트에서 7개 중 하나를 통과하지 못했다.. 아마 마지막 테스트 케이스의 배열 크기가 너무 커서 생긴 문제라고 생각되었다.
    • flat()에서 시간이 오래 소요된 것 같아서 공식 문서를 찾아보니 flat() 메소드도 어찌 됐든 모든 원소를 돌아야 하기 때문에 2차원 배열인 경우 O(N * M)의 시간 복잡도를 갖게 된다는 것을 알게 되었다.

    • 따라서 flat() 메소드 대신 다른 방법을 사용했다.

      return board.reduce(
  (acc, cur, i) => acc + cur.filter((v, j) => v + prefixSum[i][j] >= 1).length,
  0,
);

    • 통과!!

      image

    • 평소에 2차원 배열을 1차원 배열로 변환할 때 flat() 메서드를 자주 사용했는데 위와 같이 작성하면 한번 더 배열을 도는 꼴이므로 잘 생각하고 사용해야 겠다고 느꼈다.

  • 코드

    function solution(board, skill) {
  const maxX = board[0].length,
    maxY = board.length;

  const prefixSum = Array.from({ length: maxY + 1 }, () =>
    Array.from({ length: maxX + 1 }, () => 0),
  );

  skill.forEach(([type, r1, c1, r2, c2, degree]) => {
    const d = type === 1 ? -1 * degree : degree;

    prefixSum[r1][c1] += d;
    prefixSum[r2 + 1][c2 + 1] += d;
    prefixSum[r1][c2 + 1] -= d;
    prefixSum[r2 + 1][c1] -= d;
  });

  for (let y = 0; y <= maxY; y++) {
    for (let x = 1; x <= maxX; x++) {
      prefixSum[y][x] += prefixSum[y][x - 1];
    }
  }

  for (let x = 0; x <= maxX; x++) {
    for (let y = 1; y <= maxY; y++) {
      prefixSum[y][x] += prefixSum[y - 1][x];
    }
  }

  return board.reduce(
    (acc, cur, i) => acc + cur.filter((v, j) => v + prefixSum[i][j] >= 1).length,
    0,
  );
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges