링크
https://school.programmers.co.kr/learn/courses/30/lessons/49994
문제
게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.
- U: 위쪽으로 한 칸 가기
- D: 아래쪽으로 한 칸 가기
- R: 오른쪽으로 한 칸 가기
- L: 왼쪽으로 한 칸 가기
캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.
우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다.
단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.
예를 들어, "LULLLLLLU"로 명령했다면 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.
명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.
풀이
중복된 경로를 제외하고 이동한 길이를 구하는 문제이다.
이 문제에서 중요한 점은 (0, 0) -> (0, 1)과 (0, 1) -> (0, 0)는 같은 경로를 나타낸다는 것이다. 방향성의 문제만 있을 뿐, 경로 자체는 같다는 의미이다. 따라서 하나의 경로에 대해서 2가지의 처리를 해주도록 해야한다.
명령어의 종류는 총 4가지로 나올 수 있는 경우가 한정되어 있기 때문에 각각 다른 작업을 하도록 코드를 작성한다. 각 명령에 대해서 이동할 경로가 벽으로 막혀있는지(5x5를 넘어가는지) 확인이 필요하고 넘어가지 않는다면 좌표를 이동하고 두 점에 대한 오고 가는 경로를 함께 추가한다. 이 때, 경로의 추가는 set 객체를 활용해서 추가한다.
예를 들어 (0, 0) -> (0, 1)의 경우에는 '0001'과 '0100'을 함께 추가해서 같은 경로임을 의미하도록 한다.
명령어에 대해서 모두 처리가 끝나면 set으로 경로를 추가했기 때문에 중복이 알아서 자동으로 제거되므로 set의 size에서 절반이 바로 처음 걸어본 경로의 길이가 된다.
코드
// 이동한 경로에 중복을 제거하는 문제.
// set을 활용해서 시작지점 도착지점으로 문자열을 만들어 넣어줌.
// (2,3) -> (2,2)의 경우에는 2322를 set에 저장, 반대로 움직이는 경우도 저장해야하므로 2223도 함께 저장한다.
// 하나의 경로에 대해서 두개가 함께 저장되므로 전체 명령이 끝나면 set의 크기에서 /2 를 진행해서 겹치지 않는 경로의 수를 구한다.
function solution(dirs) {
let set = new Set()
let [min, max] = [-5, 5]
let [nowX, nowY] = [0, 0]
let [prevX, prevY] = [0, 0]
for(let i = 0; i < dirs.length; i++) {
const dir = dirs[i]
// 명령어의 종류에 따라서 진행할 알고리즘을 따로따로 작성한다.
if(dir === "U") {
if(nowY === max) continue
nowY++
} else if(dir === "D") {
if(nowY === min) continue
nowY--
} else if(dir === "R") {
if(nowX === max) continue
nowX++
} else if(dir === "L") {
if(nowX === min) continue
nowX--
}
set.add("" + prevX + prevY + nowX + nowY)
set.add("" + nowX + nowY + prevX + prevY)
prevX = nowX
prevY = nowY
}
return set.size / 2
}