알고리즘 스터디 40주차 - [프로그래머스] 방문 길이, 점프와 순간 이동

1. 방문 길이 (Level 2)

Problem Summary

• 명령어가 주어진다. 이 명령어대로 캐릭터는 움직이고, “처음 걸어본 길의 길이”를 구해야 한다.
• 좌표평면의 경계를 넘어가는 명령어는 무시한다.
• 캐릭터는 0,0에서 시작하고, 경계는 5, -5이다.

Solution

function solution(dirs) {
  let answer = 0;
  const loc = { x: 0, y: 0 };
  const set = new Set();

  for (const dir of dirs) {
    const curLoc = `${loc.x}${loc.y}`;
    switch (dir) {
      case 'U':
        loc.y < 5 && loc.y++;
        break;
      case 'D':
        loc.y > -5 && loc.y--;
        break;
      case 'R':
        loc.x < 5 && loc.x++;
        break;
      case 'L':
        loc.x > -5 && loc.x--;
        break;
    }
    const movedLoc = `${loc.x}${loc.y}`;
    const path = curLoc + movedLoc;
    const anotherPath = movedLoc + curLoc;

    if (!set.has(path) && !set.has(anotherPath) && curLoc !== movedLoc) {
      answer++;
      set.add(path);
      set.add(anotherPath);
    }
  }

  return answer;
}

Time Complexity

• O(N)
  • N: dirs의 길이
  • 주어진 dirs 문자열을 한 번 반복하면서 연산함
  • 입력 크기에 비례하여 선형적으로 실행 시간 증가

Another solution

function solution(dirs) {
  let loc = { x: 0, y: 0 };
  const dirMap = {
    U: { direction: 'y', value: 1 },
    D: { direction: 'y', value: -1 },
    R: { direction: 'x', value: 1 },
    L: { direction: 'x', value: -1 },
  };

  const pathSet = new Set();

  for (const dir of dirs) {
    const { direction, value } = dirMap[dir];
    const moved = loc[direction] + value;
    if (moved > 5 || moved < -5) continue;
    const movedLoc = { ...loc };
    movedLoc[direction] = moved;
    pathSet.add(`${loc.x}${loc.y}${movedLoc.x}${movedLoc.y}`);
    pathSet.add(`${movedLoc.x}${movedLoc.y}${loc.x}${loc.y}`);
    loc = movedLoc;
  }
  return pathSet.size / 2;
}

• pathSet에 방문한 길을 저장하는 방식
• answer 변수를 따로 쓸 필요가 없어짐

Result

 

2. 점프와 순간 이동 (Level 2)

Problem Summary

• 한 번에 K칸 앞으로 점프 or (현재까지 온 거리) x 2에 해당하는 위치로 순간이동
• 순간이동은 건전지 사용 안줄음 (더 효율적)
• K칸 점프는 K만큼 건전지 사용량 필요
• 거리가 N만큼 떨어져 있는 거리 가려고 함
  • 점프는 최소화 → 건전지 사용량의 최솟값

Solution

function solution(n) {
  let ans = 0;

  while (n) {
    if (n % 2) {
      ans++;
      n--;
      continue;
    }
    n = n / 2;
  }

  return ans;
}

• 주어진 값을 계속 2로 나눠 주는 접근 방식
  • 2로 나눴을 때 나머지가 있으면, -1을 한 후, 건전지 사용량을 1 증가시킨다.
  • 2로 나눴을 때 나머지가 없으면(즉 나누어 떨어지면) 순간이동한다.(2로 나눠준 값을 할당한다.)

Time Complexity

• O(log n)
  • 루프를 매번 돌 때마다 n은 2로 나눠지거나 1이 감소하게 된다. 2로 나눠지면서 n의 값이 반으로 줄어들기 때문에 시간 복잡도가 O(log n)이 된다.

Another solution

function solution(n) {
  return n.toString(2).replace(/0/g, '').length;
}

• 어떤 수를 2로 나누고, 그 몫을 또다시 2로 나누며 나오는 나머지들의 합은, 그 수를 이진수로 변환한 후의 1의 개수와 같음을 이용한 풀이

Result