[Javascript][Programmers] 방문 길이

 

문제

• 키워드: 중복 처리, 역방향

 

나의 풀이

• 시간 복잡도: O(N)

function solution(dirs) {
    // ➊ 중복 처리를 위한 Set
    const visited = new Set();
    let x = 0, y = 0;

    // ➋ 방향에 따른 좌표 변화
    const moves = {
        'U': [0, 1],
        'D': [0, -1],
        'R': [1, 0],
        'L': [-1, 0]
    };

    for (const dir of dirs) {
        const [dx, dy] = moves[dir];
        const nx = x + dx;
        const ny = y + dy;

        // ➌ 주어진 범위 내인지 확인
        if (nx >= -5 && nx <= 5 && ny >= -5 && ny <= 5) {
            const path = JSON.stringify({from: [x, y], to: [nx, ny]});
            const reversePath = JSON.stringify({from: [nx, ny], to: [x, y]});

            // ➍ 정방향 경로와 역방향 경로를 모두 확인
            if (!visited.has(path) && !visited.has(reversePath)) {
                visited.add(path);
            }

            [x, y] = [nx, ny];
        }
    }

    return visited.size;
}

moves를 사용하여 각 방향에 대한 좌표 변화를 정의하고, Set을 활용하여 이미 방문한 경로를 추적합니다. 각 이동마다 현재 위치에서 새 위치로의 경로를 문자열로 표현하여 Set에 추가하는데, 이때 역방향 경로도 함께 체크하여 중복을 방지합니다. 좌표의 경계(-5 ~ 5)를 벗어나지 않도록 확인하며, 최종적으로 Set의 크기를 반환하여 유일한 경로의 수를 얻습니다.

⚠️  문자열로 표현하여 Set에 추가: 객체는 참조 타입이므로 내용 기반 비교 시 직접 사용이 불가능

 

문제점

• JSON.stringify() 호출로 인한 성능 저하
• 하나의 함수에 집중된 기능들

 

다른 풀이

function isValidMove(nx, ny) {
  // ➊ 좌표평면을 벗어나는지 체크하는 함수
  return nx >= -5 && nx <= 5 && ny >= -5 && ny <= 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];
  }
}

function solution(dirs) {
  let x = 0;
  let y = 0;

  const visited = new Set(); // ➌ 겹치는 좌표는 1개로 처리하기 위함
  for (const dir of dirs) {
    // ➍ 주어진 명령어로 움직이면서 좌표 저장
    const [nx, ny] = updateLocation(x, y, dir);

    if (!isValidMove(nx, ny)) {
      // ➎ 벗어난 좌표는 인정하지 않음
      continue;
    }

    // ➏ A에서 B로 간 경우 B에서 A도 추가해야 함(총 경로의 개수는 방향성이 없음)
    visited.add(`${x}${y}${nx}${ny}`);
    visited.add(`${nx}${ny}${x}${y}`);

    [x, y] = [nx, ny]; // ➐ 좌표를 이동했으므로 업데이트
  }

  return visited.size / 2;
}

• 별도의 확인 과정 없이 정방향 경로와 역방향 경로를 동시에 추가하고, 최종 이동 길이를 2로 나눔

 

---

Reference

코딩테스트 합격자 되기: 자바스크립트 편