[자바스크립트, js] 프로그래머스 방문길이

안녕하세요,

 

오늘은 난이도 2의 '방문길이'를 가져왔습니다!! 

 

풀었던 저의 주관적인 풀이를 공유하고자 합니다!

---

 문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U: 위쪽으로 한 칸 가기
• D: 아래쪽으로 한 칸 가기
• R: 오른쪽으로 한 칸 가기
• L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

예를 들어, "ULURRDLLU"로 명령했다면

• 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.

• 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)

단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

예를 들어, "LULLLLLLU"로 명령했다면

• 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.

이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

---

제한사항

• dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
• dirs의 길이는 500 이하의 자연수입니다.

---

입출력 예

 

dirs	answer
"ULURRDLLU"	7
"LULLLLLLU"	7

---

해당 문제는, 단순하게 경로만 기억하고 있으면 된다 라고 생각했습니다. 경로를 확인하는 방법은 총 두가지를 생각했었는데, 첫번째로는 점(0, 0)같이 점을 기억 두번째로는 선을 기억 (0 -> 1) 입니다.

 

하지만 첫번째의 문제점이 있었죠.. (0, 0)에서 (0, 1) 로 이동을 했을 때 (0, 0)을 방문한 것으로 체크를 한다면 (-1, 0)에서 (0, 0)으로 방문하는 것도 이미 방문했던 것으로 파악을 하는 것이죠.

 

그래서 사용한 방식이 이동한 간선을 체크하자! 입니다. 간선을 체크하는 방식으로는 (0, 0) 에서 (0, 1)로 이동했을때의 간선을 저장하는 것인데, 여기서 만약 0, 0 - 0, 1 의 간선만 체크한다면 반대의 경우인 (0, 1)에서 (0, 0)으로 가는 간선은 방문하지 않은 것으로 되는 것이죠.

 

그럼, 어떻게 해야할까요? (0, 1) 에서 (0, 0)으로 가는 간선도 저장, (0, 0)에서 (0, 1)로 가는 간선도 저장하면 되는 것입니다. 저장하는 방식은 array.push 를 통해 배열에 저장할 수 있지만, 해당 방식은 중복 체크를 따로 해야하기 때문에 좋지 않을 것 같고 저는 set.add 를 사용해 저장하도록 하겠습니다.

 

이동한 경로를 저장, 추후에 이동한 경로들의 / 2의 값을 토대로 값을 도출할 수 있습니다. '/ 2'를 하는 이유는 우리가 0 -> 1과 1 -> 0의 간선 총 2개를 저장했기 때문에 / 2를 해주는 것입니다.

 

function solution(dirs) {
  let position = [0, 0]
  let move = { U: [0, 1], D: [0, -1], R: [1, 0], L: [-1, 0] }
  let route = new Set()


  for (let dir of dirs) {
    const [x, y] = [position[0] + move[dir][0], position[1] + move[dir][1]]
    if (x > 5 || x < -5 || y > 5 || y < -5) continue
    route.add('' + position[0] + position[1] + '' + x + y)
    route.add('' + x + y + '' + position[0] + position[1])
    position = [x, y]
  }

  return route.size / 2;
}

위처럼 set.add 를 사용해 중복 제거.. 구우웃.. 혹시 set에 대해 잘 모르겠다면 제 포스팅 중에 set에 관련된 포스팅이 있기에.. 많은 참고 부탁드립니다 .ㅎ..

 

여기까지.. 방문길이 문제였습니다!!

 

다른 풀이들도 한번 방문해주세요~

 

한솔방울 깃허브

 

이상 감사합니다!!