[ 프로그래머스 / JavaScript ] 방문 길이

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)로 이루어져 있습니다.

예를 들어, "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

 

 

입출력 예 설명

---

입출력 예 #1
문제의 예시와 같습니다.

 

입출력 예 #2
문제의 예시와 같습니다.

 

 

나의 풀이

---

U, D, R, L에 따라 인덱스 x, y좌표 값 변환 전을 start에 넣어준 뒤, 값 변환된 것을 end에 넣어주었다. 만약 지도의 범위를 벗어나지 않았다면 방문한 길인지 확인을 하고 방문을 하지 않았다면 count에 1을 더해주었다. 그리고 end의 값을 start에 넣어주었다. 

 

문제를 풀고 최종 테스트를 돌렸을 때 다수가 통과가 되지 않았다. 나의 토드를 다시 보니 boundary 확인하는 부분에서 이동한 부분인 end를 확인해야 하는데 이동하기 전인 current의 index를 확인하고 있어 boundary에서 벗어나도 count를 하고 있었던 것이다. 이 부분을 해결해주니 바로 통과되었다.

 

function solution(dirs) {
    let count = 0;
    let current = [0, 0];
    const direction = {
        "U": [0, 1],
        "D": [0, -1],
        "R": [1, 0],
        "L": [-1, 0]
    }
    let visited = [];
    for(let i = 0; i < dirs.length; i++) {
        let [x,y] = direction[dirs[i]];
        let start = current; 
        let end = [Number([current[0] + x]),Number(current[1] + y)];
        if(end[0] > 5 || end[0] < -5 || end[1] > 5 || end[1] < -5) {
            continue;
        }
        const isVisited = visited.find((item) => {
            if( (item[0][0] === start[0] && item[0][1] === start[1] && item[1][0] === end[0] && item[1][1] === end[1])
               || (item[0][0] === end[0] && item[0][1] === end[1] && item[1][0] === start[0] && item[1][1] === start[1]) ) {
                return true;
            }
        })
        if( !isVisited ) {
            ++count;
            visited.push([start, end]);
        }
        current = end;
    }
    return count;
}

 

 

 

다른 풀이

---

아래의 코드가 나의 코드에 비해 훨씬 효율적이다. 아래의 코드에서 Map() 메서드를 사용하였다.

 

Array.Map()은 key-value 페어(pair)로 이루어져 있다.

• key를 사용해서 value를 get, set 할 수 있다.
• key 들은 중복될 수 없다: 하나의 key 에는 하나의 value 만 존재한다.

move 함수에서는 dirs에서 움직일 경로들을 계산해서 이동한 좌표의 값을 리턴해준다. 반환된 값을 moved에 저장한 뒤 boundary에서 벗어나지 않았다면 firstPathMap에 넣어주었다. 그리고 이동한 좌표의 값을 현재의 위치로 바꿔주었다. 마지막에 Map.size로 처음 방문한 길의 개수를 리턴하여 주었다.

 

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])}`;
}