문제

완전탐색 + Set

오늘의 문제

문제 풀이

접근

간단히 배열에 저장해서 전체 배열 탐색 후 집어넣기..? => 효율 별로
이미 걸어본 것인지 확인하기 위해 Set 을 사용한다
음수와 양수가 섞이는 값은 계산하기 복잡하므로, 시작점을 0,0 에서 5,5 로 이동한다.

의사코드 및 설계과정

좌표 원점을 변경한다.
다음 좌표만 계산한다.
경계 내부에 있는지 판단한다.
메인 루프를 처리한다.

추가적으로 한 개의 함수는 하나의 기능만 담당할 수 있도록 한다.

풀이 1

자세한 설명은 코드를 작성하며 기록한 주석이 도움이 될 듯 하다.

function solution(dirs) {
  // 처음 걸어본 곳만 중요하다.
  const visited = new Set();

  let curLoc = [5, 5];

  // 하나씩 처리한다.
  for (dir of dirs) {
    // 새롭게 이동할 곳을 설정해준다.
    const [x, y] = [...curLoc];
    let [nx, ny] = move(dir, ...curLoc);
    const isValid = checkMove(nx, ny);

    // 불가능한 이동은 넘어간다.
    if (!isValid) continue;

    // 가능한 경우만 남는다.
    // 한번이라도 방문한 경우 (해당 길을 걸어봄)는 미리 반대 경우를 추가하여 해소한다.
    visited.add(`${x}${nx}-${y}${ny}`);
    visited.add(`${nx}${x}-${ny}${y}`);
    curLoc = [nx, ny];
  }
  return visited.size / 2;
}

// 다음 이동이 내부에 있는지 확인 -5 5, -5 -5 , 5,5 5,-5 로 이루어진 좌표평면
// 원점을 5,5 로 변경하자 -> 음수 판단이 귀찮은 문제.
// 즉 [0,0], [0,10], [10,10], [10,-10]이 새로운 범위가 된다
function checkMove(nx, ny) {
  const isValidX = nx >= 0 && nx <= 10;
  const isValidY = ny >= 0 && ny <= 10;

  return isValidX && isValidY;
}

// 움직인 결과를 리턴해주는 곳
function move(dir, x, y) {
  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];
    default:
      return;
  }
}

리팩터링 (경로 정규화)

처음 작성된 코드에서는 불필요하게 2개를 저장하고, 결과에서 2로 나눠 반환하는 사소한 성능 누수가 있었다.

이를 해결하기 위해 저장하는 경로를 정규화 할 수 있도록 리팩터링 목표를 잡았다.

따라서 다음과 같은 변경 사항이 생겼다.

기존 경로 저장 로직

visited.add(`${x}${nx}-${y}${ny}`);
visited.add(`${nx}${x}-${ny}${y}`);
curLoc = [nx, ny];

변경된 경로 저장 로직

const key1 = `${x},${y}`;
const key2 = `${nx},${ny}`;

let uniquePath;

// 자바스크립트에서는 사전순 정렬이므로 이를 활용한다.
if (key1 < key2) {
  uniquePath = `${key1}-${key2}`;
} else {
  uniquePath = `${key2}-${key1}`;
}

visited.add(uniquePath);
curLoc = [nx, ny];

살짝 길어지기는 했지만, 구분자를 활용하여 확실하게 저장할 수 있도록 하고,

사전순 정렬을 활용하여, 중복되는 경우를 미리 처리하여 저장할 수 있게 했다.

최종 코드

function solution(dirs) {
  // 처음 걸어본 곳만 중요하다.
  const visited = new Set();

  let curLoc = [5, 5];

  // 하나씩 처리한다.
  for (dir of dirs) {
    // 새롭게 이동할 곳을 설정해준다.
    const [x, y] = [...curLoc];
    let [nx, ny] = move(dir, ...curLoc);
    const isValid = checkMove(nx, ny);

    // 불가능한 이동은 넘어간다.
    if (!isValid) continue;

    // 가능한 경우만 남는다.
    // 한번이라도 방문한 경우 (해당 길을 걸어봄)는 미리 반대 경우를 추가하여 해소한다.
    // 정규화를 진행해보자
    const key1 = `${x},${y}`;
    const key2 = `${nx},${ny}`;

    let uniquePath;

    // 자바스크립트에서는 사전순 정렬이므로 이를 활용한다.
    if (key1 < key2) {
      uniquePath = `${key1}-${key2}`;
    } else {
      uniquePath = `${key2}-${key1}`;
    }

    visited.add(uniquePath);
    curLoc = [nx, ny];
  }
  return visited.size;
}

// 다음 이동이 내부에 있는지 확인 -5 5, -5 -5 , 5,5 5,-5 로 이루어진 좌표평면
// 원점을 5,5 로 변경하자 -> 음수 판단이 귀찮은 문제.
// 즉 [0,0], [0,10], [10,10], [10,-10]이 새로운 범위가 된다
function checkMove(nx, ny) {
  const isValidX = nx >= 0 && nx <= 10;
  const isValidY = ny >= 0 && ny <= 10;

  return isValidX && isValidY;
}

// 움직인 결과를 리턴해주는 곳
function move(dir, x, y) {
  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];
    default:
      return;
  }
}

마무리하며

첫 문제 해결 이후의 개선이 성공적인 것 같아서 마음에 든다.

무작정 코드를 작성하는 것 보다 의사코드, 설계 그리고 함수로 분리하며 내 코드를 고쳐나가는 과정이 꽤나 매력적이었고, 효율적이라고 생각됐다.

아!

화이팅!

-뱅-

[Node.js] 프로그래머스 - 방문 길이

조금 이쁘게 생긴 코드.

문제