[구름LEVEL] 블록 게임 | 자바스크립트 JS | 스택/큐, 구현 | Lv2

문제

 

풀이 과정

첫 번째 입력 예시인

5
RRULD
5 2 4 3 2
를 기준으로 답인 3이 나오기까지의 과정을 그려보자면 위와 같다. 시작점 (0, 0)에는 1점이 있고, 방향 커맨드를 따라 빈 곳에 블럭을 놓다가 이미 채워진 공간이 있으면 해당 블럭이 놓여지기 직전 시점으로 '뒤로 감기'를 하듯 쌓았었던 블럭을 제거해야한다.

즉, N 번째 블럭을 쌓기 위해 M 번째 블럭을 제거해야한다면 M에서 ~ N-1 번째 블럭을 없애야 하므로 다음과 같은 접근으로 풀었다.

 

1.  LRUD 키워드를 바탕으로 이동할 방향의 정보가 담긴 dirDict 객체를 생성한다.

2.  queue에 첫 번째 블록인 [0, 0, 1]을 넣는다. queue에는 현재 쌓인 블록들의 정보를 [x좌표, y좌표, score] 배열들로 저장할 것이다.

3.  블록을 쌓을 방향이 담긴 배열(dirLst)에서 for문으로 하나씩 꺼내 다음 탐색 지점인 nr과 nc를 업데이트한다.

4.  queue에 다음 탐색 지점에 해당하는 블록이 있는지 검사한다.

    4-1.  있을 경우 : queue에서 0부터 해당 블록의 idx - 1까지의 범위만을 남긴다.

    4-2.  없을 경우 : queue에 [nr, nc, 점수] 원소를 추가한다

5.  reduce로 queue의 score들을 합산하여 답을 출력한다.

 

작성 코드

// Run by Node.js
const readline = require('readline');

const dirDict = {  // [1] 이동할 방향의 정보가 담긴 dirDict 객체
  L: [0, -1],
  R: [0, 1],
  U: [-1, 0],
  D: [1, 0]
}
let N, dirLst;

const solution = (scores, dirLst, N) => {
  let q = [[0, 0, 1]];  // [2] 현재 쌓인 블록들의 정보를 [x좌표, y좌표, score] 배열들로 저장
  let dr, dc, r, c, nr, nc;
  for (i = 0; i < N; i++) {
    // [3] 다음 탐색 지점인 nr과 nc를 업데이트
    nr = q[q.length - 1][0] + dirDict[dirLst[i]][0];
    nc = q[q.length - 1][1] + dirDict[dirLst[i]][1];
		
    q.forEach((block, idx) => { // [4] 다음 탐색 지점에 해당하는 블록이 있는지 검사
      if (block[0] === nr && block[1] === nc) {
        q = q.slice(0, idx)  // [4-1] 있을 경우, 해당 블럭을 포함하여 이후에 쌓인 블럭들 없애기
      }
    })
		
    q.push([nr, nc, scores[i]]);  // [4-2] 없을 경우, q에 추가
  }
  
  // [5] 좌표에 쌓인 블럭들의 score 합치기
  return q.reduce((sm, block) => sm + block[2], 0);
}

(async () => {
  let rl = readline.createInterface({ input: process.stdin });
	
  for await (const line of rl) {
    if (!N) {
      N = +line;
    } else if (!dirLst) {
      dirLst = line;
    } else {
      const scores = line.split(' ').map(Number);
      console.log(solution(scores, dirLst, N));
      rl.close();
    }
  }
	
  process.exit();
})();

 

 

문제 링크

구름LEVEL