방문길이

내 풀이법

문제해석

• 게임 캐릭터의 이동거리를 구하라!
• 제한사항
  • 위 그림의 좌표면을 넘어설 수가 없음! (최대 5 최소 -5)
  • 처음 걸어본 거리만 이동거리로 해당됨!

 

내가 생각한 풀이법

• 각 이동(up, down, left, right)마다 값을 변경하는 함수를 작성한다
• [제한사항1] 이동한 루트가 중복 안됨
  • set객체를 사용해야겠다고 생각함
  • [0, 0] 좌표에서 [0, 1] 좌표로 이동을 "0001"로 string으로 값을 주고 이를 set 객체에 넣음
  • [0, 0] 좌표에서 [0, 1] 좌표로 이동 ("0001")과 [0, 1] 좌표에서 [0, 0] 좌표로 이동함 ("0100")은 루트 상 똑같기에 두 값 모두 set 객체에 넣어야함. (그러므로 마지막에 set.size()를 2로 나누어야함)

• [제한사항2] 위 그림의 좌표면을 넘을 수 없음
  • 각 이동(up, down, left, right)마다 값을 변경하는 함수에 if문을 통해 5를 넘어갈 시 변경사항이 없도록 함
  • 변경사항이 없으면 "0101" [0, 1]에서 [0, 1]로 이동과 같은 값이 생길 수 있기에 이와 같은 값은 set객체에 못 넣도록 함

나의 코드

function solution(dirs) {
  let answer = new Set();
  let roadCord;

  function up(cordinate) {
    if (cordinate[1] === 5) {
      return cordinate;
    }

    return [cordinate[0], cordinate[1] + 1];
  }
  function down(cordinate) {
    if (cordinate[1] === -5) {
      return cordinate;
    }
    return [cordinate[0], cordinate[1] - 1];
  }
  function right(cordinate) {
    if (cordinate[0] === 5) {
      return cordinate;
    }
    return [cordinate[0] + 1, cordinate[1]];
  }
  function left(cordinate) {
    if (cordinate[0] === -5) {
      return cordinate;
    }
    return [cordinate[0] - 1, cordinate[1]];
  }

  for (let i = 0; i < dirs.length; i++) {
    // phase 1: 현재 위치 좌표
    if (i === 0) {
      roadCord = [0, 0];
    } else {
      roadCord = [roadCord[2], roadCord[3]];
    }

    // phase 2: 이동 방향 위치 좌표
    if (dirs[i] === "U") {
      roadCord.push(...up(roadCord));
    } else if (dirs[i] === "D") {
      roadCord.push(...down(roadCord));
    } else if (dirs[i] === "R") {
      roadCord.push(...right(roadCord));
    } else if (dirs[i] === "L") {
      roadCord.push(...left(roadCord));
    }

    // phase 3: 이동한 루트를 set객체에 저장
    if (!(roadCord[0] === roadCord[2] && roadCord[1] === roadCord[3])) {
      let road1 =
        `${roadCord[0]}` +
        `${roadCord[1]}` +
        `${roadCord[2]}` +
        `${roadCord[3]}`;
      answer.add(road1);
      let road2 =
        `${roadCord[2]}` +
        `${roadCord[3]}` +
        `${roadCord[0]}` +
        `${roadCord[1]}`;
      answer.add(road2);
    }
  }
  return answer.size / 2;
}

코드특징

• 전역변수 roadCord는 현재 좌표와 이동한 좌표 값을 배열로 표현하고자 했다. ex) [0, 0, 0, 1] x: 0 y: 0 좌표에서 x: 0 y: 1 좌표로 이동
• 이동(up, down, left, right)마다 좌표 값을 변경하는 함수를 작성한다. 해당 함수에 좌표면을 넘어갈 시 기존 값을 리턴하도록 한다.
• 위 코드의 for 문은 세 페이즈로 나눠서 볼 수 있다
  1. 현재 좌표값을 roadCord에 준다. 처음은 [0, 0]으로 시작한다
  2. 이동할 방향에 따라 현재 좌표값에 이동해야할 거리를 더하고 해당 값을 기존 roadCord에 push를 한다.
     • 현재 좌표가 [0, 0]에서 Up을 만나 [0, 1] 좌표로 바뀜을 roadCord = [0, 0, 0, 1]로 표현
  3. 만약 이동을 했다면 roadCord의 배열 값을 string으로 나타낸 후 set 객체에 넣는다.
     • [0, 0] 좌표에서 [0, 1] 좌표로 이동 ("0001")과 [0, 1] 좌표에서 [0, 0] 좌표로 이동함 ("0100")은 지도에서 봤을 때 루트 상 똑같기에 두 값 모두 set 객체에 넣어야함.
• set 객체의 size값을 2로 나눈 값을 반환한다.
• 중복되는 코드가 많다...

코드성능

• 성능은 꽤 괜찮다!

다른 사람 풀이법 1

function solution(dirs) {
  const move = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };

  let check = new Set();
  let now = [0, 0];

  for (let i = 0; i < dirs.length; i++) {
    let nx = now[0] + move[dirs[i]][0];
    let ny = now[1] + move[dirs[i]][1];

    if (nx > 5 || nx < -5 || ny > 5 || ny < -5) continue;

    check.add("" + now[0] + now[1] + nx + ny);
    check.add("" + nx + ny + now[0] + now[1]);

    now = [nx, ny];
  }
  return check.size / 2;
}

코드특징

• 나의 풀이방법과 유사하지만 코드가 매우 클린하다
• 이동방향을 나는 함수로 표현했지만 위 코드는 Object 객체로 표현함
  • 키를 이동 방향, 값을 이동 방향의 좌표로 나타냄
  • move["U"]와 같이 이동해야할 거리에 접근

• if (nx > 5 || nx < -5 || ny > 5 || ny < -5) continue;
  • 만약 좌표면을 넘어가면 continue를 통해 넘어감

코드성능

• 나의 코드보다 약간 더 빠르다. 아마 나의 코드는 불필요한 함수도 있어서 그런듯 싶다

다른 사람 풀이법 2

function solution(dirs) {
    const firstPathMap = new Map();
    let now = [0, 0];
    let moved;
    for(let dir of dirs) {
        moved = move(now, dir);
        if(moved[0] < -5 || moved[0] > 5 || moved[1] < -5 || moved[1] > 5) {
            continue;
        }
        firstPathMap.set(generateKey(now, moved), true);
        now = moved;
    }  

    return firstPathMap.size;
}

function move(now, dir) {
    switch(dir) {
        case 'L': 
            return [now[0] - 1, now[1]];
        case 'R':
            return [now[0] + 1, now[1]];
        case 'U':
            return [now[0], now[1] + 1];
        case 'D':
            return [now[0], now[1] - 1];
    }        
}

function generateKey(now, moved) {
    return `${Math.min(now[0], moved[0])},${Math.max(now[0], moved[0])},${Math.min(now[1], moved[1])},${Math.max(now[1], moved[1])}`;
}

코드특징

1. Map 객체를 사용함
   • Map.prototype.set을 통해 map 객체에 key값과 value값을 한쌍으로 받음.
   • key값이 기존 map객체 내에 있는 key값과 중복되는 경우 에러없이 무시되는 특성이 있음
   • 이 특성을 활용하여 중복되는 경우 걸러냄

1. generateKey 함수
   • 문제 특성 상 [0, 0] 좌표에서 [0, 1] 좌표로 이동 ("0001")과 [0, 1] 좌표에서 [0, 0] 좌표로 이동함 ("0100")은 같음
   • 이 문제를 해결하기 위해 위 함수를 활용

1. move 함수
   • 이동할 때의 동작을 move 함수로 나타냄

코드성능

• 나의 코드보다 약간 빠르다!

오늘 배운점

• Map 객체 사용방법에 대하여 알게됨
• 코드중복이 많은 경우 정리할 방법은 많다! 다음에는 코드가 복잡하다고 느껴지면 한번 정리해보자