[JS][백준]5549_행성 탐사

문제 번호

5549번: 행성 탐사

 

 

알고리즘 분류

• 누적 합

 

문제 풀이

 2차원 배열혹은 3차원 배열을 사용해서 누적 합을 구해야한다. 이번에는 2차원 배열을 사용했다. 각 2차원 배열의 [i][j]는 (1,1)부터 (i,j)까지의 J O I 의 갯수를 나타낸다.

let sumJ = new Array(1001).fill(null).map(_ => new Array(1001).fill(0));
let sumO = new Array(1001).fill(null).map(_ => new Array(1001).fill(0));
let sumI = new Array(1001).fill(null).map(_ => new Array(1001).fill(0));

 누적합을 구하기위해서 2차원 배열을 채워넣는다. 배열을 채워넣는 방법은 다음과 같다. 예를들어 J가 몇개 있는지 구하는 방법은 다음식을 사용한다.

sumJ[i][j] = sumJ[i-1][j] + sumJ[i][j-1] - sumJ[i-1][j-1] + ( map[i][j] === 'J'? 1 : 0)

 

그림으로 보면,

1	2
3	4

 4번을 채워넣기 위해서는 (1+3) + (1+2) - 1 + (4번이 J라면 '1', 아니면 '0') 이다.

누적합을 세로로, 가로로 모두 구한다고 생각하면된다. 그리고 4번영역을 구할때는 가로,세로 누적합을 모두 더해야하는데 1번은 중복으로 더해진다. 그래서 중복되는 1번을 한번 빼주고 4번에 해당하는 영역이 구하고자하는 누적합과 일치한다면 1을, 일치하지 않는다면 0을 더해주는것이다.

function makeSum(map) { // 10^6.
  for (let i = 1; i <= M; i++) { // 1000
    for (let j = 1; j <= N; j++) { // 1000
      if (map[i][j] === 'J') {
        sumJ[i][j] = sumJ[i - 1][j] + sumJ[i][j - 1] - sumJ[i - 1][j - 1] + 1;
        sumO[i][j] = sumO[i - 1][j] + sumO[i][j - 1] - sumO[i - 1][j - 1];
        sumI[i][j] = sumI[i - 1][j] + sumI[i][j - 1] - sumI[i - 1][j - 1];
      }
      else if (map[i][j] === 'O') {
        sumJ[i][j] = sumJ[i - 1][j] + sumJ[i][j - 1] - sumJ[i - 1][j - 1];
        sumO[i][j] = sumO[i - 1][j] + sumO[i][j - 1] - sumO[i - 1][j - 1] + 1;
        sumI[i][j] = sumI[i - 1][j] + sumI[i][j - 1] - sumI[i - 1][j - 1];
      }
      else if (map[i][j] === 'I') {
        sumJ[i][j] = sumJ[i - 1][j] + sumJ[i][j - 1] - sumJ[i - 1][j - 1];
        sumO[i][j] = sumO[i - 1][j] + sumO[i][j - 1] - sumO[i - 1][j - 1];
        sumI[i][j] = sumI[i - 1][j] + sumI[i][j - 1] - sumI[i - 1][j - 1] + 1;
      }
    }
  }
}

 2차원배열 3개를 사용하지않고 3차원배열 1개를 사용해서 모든 누적합을 하나의 배열에 저장할 수 도 있다.

SUM[3][1001][1001].

 

 이제 문제에서 주어지는 입력을 받아서 해당구간에 각 영역이 몇개있는지 확인하면된다.

function sol(a, b, c, d) { // 10^5.
  let J = 0, O = 0, I = 0;
  J = sumJ[c][d] - sumJ[c][b - 1] - sumJ[a - 1][d] + sumJ[a - 1][b - 1];
  O = sumO[c][d] - sumO[c][b - 1] - sumO[a - 1][d] + sumO[a - 1][b - 1];
  I = sumI[c][d] - sumI[c][b - 1] - sumI[a - 1][d] + sumI[a - 1][b - 1];

  return `${J} ${O} ${I}`;
}

 

전체코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const [M, N] = input[0].split(' ').map(Number); // 세로, 가로
const K = +input[1];

let sumJ = new Array(1001).fill(null).map(_ => new Array(1001).fill(0));
let sumO = new Array(1001).fill(null).map(_ => new Array(1001).fill(0));
let sumI = new Array(1001).fill(null).map(_ => new Array(1001).fill(0));

function makeSum(map) { // 10^6.
  for (let i = 1; i <= M; i++) { // 1000
    for (let j = 1; j <= N; j++) { // 1000
      if (map[i][j] === 'J') {
        sumJ[i][j] = sumJ[i - 1][j] + sumJ[i][j - 1] - sumJ[i - 1][j - 1] + 1;
        sumO[i][j] = sumO[i - 1][j] + sumO[i][j - 1] - sumO[i - 1][j - 1];
        sumI[i][j] = sumI[i - 1][j] + sumI[i][j - 1] - sumI[i - 1][j - 1];
      }
      else if (map[i][j] === 'O') {
        sumJ[i][j] = sumJ[i - 1][j] + sumJ[i][j - 1] - sumJ[i - 1][j - 1];
        sumO[i][j] = sumO[i - 1][j] + sumO[i][j - 1] - sumO[i - 1][j - 1] + 1;
        sumI[i][j] = sumI[i - 1][j] + sumI[i][j - 1] - sumI[i - 1][j - 1];
      }
      else if (map[i][j] === 'I') {
        sumJ[i][j] = sumJ[i - 1][j] + sumJ[i][j - 1] - sumJ[i - 1][j - 1];
        sumO[i][j] = sumO[i - 1][j] + sumO[i][j - 1] - sumO[i - 1][j - 1];
        sumI[i][j] = sumI[i - 1][j] + sumI[i][j - 1] - sumI[i - 1][j - 1] + 1;
      }
    }
  }
}
function sol(a, b, c, d) { // 10^5.
  let J = 0, O = 0, I = 0;
  J = sumJ[c][d] - sumJ[c][b - 1] - sumJ[a - 1][d] + sumJ[a - 1][b - 1];
  O = sumO[c][d] - sumO[c][b - 1] - sumO[a - 1][d] + sumO[a - 1][b - 1];
  I = sumI[c][d] - sumI[c][b - 1] - sumI[a - 1][d] + sumI[a - 1][b - 1];

  return `${J} ${O} ${I}`;
}
function main() {
  let answer = '';

  let map = [];
  map.push([]);
  for (let i = 1; i <= M; i++) { // (1,1)부터 사용하기위해서 의미없는 'A'를 추가했다.
    let temp = 'A' + input[i + 1];
    map.push(temp.trim().split(''));
  }
  makeSum(map);

  for (let i = M + 2; i < M + 2 + K; i++) {
    let [a, b, c, d] = input[i].split(' ').map(Number); // 왼위, 오른아래.
    answer += sol(a, b, c, d) + '\n';
  }

  console.log(answer.trim())
}
main();

 

 

특이사항

 첫 시도때는 가로로 누적합만 구하고 매 줄마다 영역의 개수를 따로 구해서 시간초과에 걸렸다. 2차원 누적합은 처음 사용해보는데 3차원과 잘 써보자.