7. Character Movement Path

방문한 고유한 경로의 수를 계산

algorithm test

07. Unique Movement Path

Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.130.


Problem solving


① The first way to solve the problem : 단계별 사용자 수 계산 후, 직접 실패율 계산

function isValidMove(nx, ny) {
  return nx >= -5 && nx <= 5 && ny >=-5 && ny <=5;
  // 좌표는 -5, 5 사이의 값을 가질 수 있습니다. 이 범위를 벗어날 경우, 유효하지 않은 이동으로 간주됩니다.
}

function updateLocation(x, y, dir) {
  switch ((dir)) {
    case "U":
      return [x, y + 1];
    case "D":
      return [x, y - 1];
    case "R":
      return [x + 1, y];
    case "L":
      return [x - 1, y];
  }
  // 이 함수는 현재위치(x, y)와 주어진 방향(dir)에 따라 새로운 좌표를 계산하여 반환합니다.
}

function solution(dirs) {
  let x = 0;
  let y = 0;
  // (x, y)는 시작 위치 (0, 0)입니다.
  const visited = new Set();
  // 이미 방문한 경롤르 저장할 Set 객체를 생성 
  // Set: 중복된 경로를 저장하지 않기 위해 사용됩니다. Set은 동일한 값을 여러번 저장하지 않으므로, 방문한 경로를 고유하게 관리할 수 있습니다.
  for (const dir of dirs) {
  // 주어진 dirs 문자열의 각 문자(방향)를 하나씩 순회합니다.
  // dir: 현재 반복 중인 방향을 나타냅니다. 방향은 "U", "D", "R", "L"중 하나일 수 있습니다. 
    const [nx, ny] = updateLocation(x, y, dir);
  // updateLocation 함수를 호출하여, 현재 위치(x, y)에서 dir 방향으로 이동한 후의 새로운 위치(nx, ny)를 계산합니다. 
  // nx, ny: 새로운 위치의 좌표입니다. updateLocation 함수는 입력된 방향에 따라 새로운 좌표를 반환합니다. 
  if(isValidMove(nx, ny)) {
  // isValidMove(nx, ny) 이 함수는 주어진 좌표(nx, ny)가 -5에서 5 사이의 범위 내에 있는지 확인합니다.
      continue;
  // 범위를 벗어나면 continue 문을 실행하여, 현재 반복을 건너뛰고 다음 방향으로 넘어갑니다. 이 경우, 위치가 업데이트되지 않고 다음 방향으로 진행합니다.
    }
    visited.add(`${x}${y}${nx}${ny}`);
    visited.add(`${nx}${ny}${x}${y}`);
  // visited.add(): 경로를 문자열로 결합하여 Set에 저장합니다. 이때, 두 가지 방향을 모두 저장하영 경로의 양방향을 고려합니다. 
  // ex) (0. 0)에서 (0, 1)로 이동했다면, visited에는 "0001"과 "0100"이 모두 저장됩니다. 이를 통해 경로의 양방향을 모두 고려합니다. 
    [x, y] = [nx, ny];
  // [x, y] = [nx, ny], 배열구조분해 할당을 사용하여, 새로운 좌표로 현재 위치를 업데이트합니다. 
  }
  return visited.size/2;
  // visited.size / 2: visited Set의 크기를 2로 나누는 이유는, 각 경로를 양방향으로 저장했기 때문입니다. 실제 고유 경로의 수는 Set의 크기를 반으로 나눈 값이 됩니다. 
}

🧐 시간복잡도는 어떨까?

[Done] exited with code=0 in 0.063 seconds