[프로그래머스] 빛의 경로 사이클 - JavaScript

Yeonsu Summer·2023년 1월 8일

알고리즘

목록 보기

21/24

1. 문제

86052 문제 보러가기

2. 오답

내가 생각한 과정

시작방향에 따라 다른 값을 저장하기 위해 상하좌우 4개 원소의 배열을 만든다.
알파벳이 적힌 격자와 화살표가 그려질 공간을 모두 그리드로 작성해 각 배열에 저장한다.
해당 그리드는 1로 초기화한다.
(1, 1)에 위치한 알파벳에서 시작한다.
위쪽이나 오른쪽으로 이동하면 2를 곱한다.
아래쪽이나 왼쪽으로 이동하면 -2를 곱한다.
시작방향을 달리해 반복한다.
4가지 배열 중 중복을 없앤다.
남은 배열에서 각각 경로 길이를 구한다.
2 또는 -2인 경우 1을 더하고 4인 경우 2를 더한다.

간과한 점

만약 ["SSS", "SSS", "SSS"]인 경우가 있다면 답은 [3,3,3,3,3,3,3,3,3,3,3,3]가 되어야한다.
하지만 나의 방식대로 풀어보면 [3,3,3,3]이 나온다.

(1, 1)에 위치한 알파벳에서 시작하는 경우만 생각했기 때문이다.

grid와 grid의 각 문자열의 길이는 최대 500이므로, 나는 최대 250000번 반복문을 실행해야 한다.

당연히 시간초과가 날 것이기 때문에 다른 방식을 생각해보았다.

3. 최종 풀이

function solution(grid) {
  const direction = [
    { x: 1, y: 0 },
    { x: 0, y: 1 },
    { x: -1, y: 0 },
    { x: 0, y: -1 }, 
  ];

  function createBoard(grid) {
    const board =[];
    for (let x = 0; x < grid.length; x++) {
      board.push([]);
      for (let y = 0; y < grid[0].length; y++) {
        board[x].push(new Array(4).fill(true));
      }
    }
    return board;
  }

  function recordRoute(xi, yi, ri) {
    let total = 0;

    while (true) {
      if (!board[xi][yi][ri]) break;
      board[xi][yi][ri] = false;
      total += 1;

      xi += direction[ri].x;
      yi += direction[ri].y;

      if (xi < 0) xi = board.length - 1;
      if (xi >= board.length) xi = 0;
      if (yi < 0) yi = board[0].length - 1;
      if (yi >= board[0].length) yi = 0;

      if (grid[xi][yi] === 'R') ri = [3, 0, 1, 2][ri];
      if (grid[xi][yi] === 'L') ri = [1, 2, 3, 0][ri];
    }

    return total;
  }

  const totalList = [];
  const board = createBoard(grid);
  board.forEach((x, xi) => {
    x.forEach((y, yi) => {
      y.forEach((route, ri) => {
        if (route) {
          totalList.push(recordRoute(xi, yi, ri));
        }
      });
    });
  });

  return totalList.sort((a, b) => a - b);
}