[프로그래머스] 방문 길이 (Lv 2) - javascript

문제

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

• U: 위쪽으로 한 칸 가기

• D: 아래쪽으로 한 칸 가기

• R: 오른쪽으로 한 칸 가기

• L: 왼쪽으로 한 칸 가기

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

나의 풀이

function solution(dirs) {

    let pass = []; // 가본 경로 저장 [현재, 다음]
    let current = [0,0]; // 현재 위치
    let next = [0,0]; // 다음 위치

    for(let i = 0; i < dirs.length; i++) {

        // 1. 이동해서 next에 저장
        if (dirs[i] === 'U') next[1] ++;
        if (dirs[i] === 'D') next[1] --;
        if (dirs[i] === 'R') next[0] ++;
        if (dirs[i] === 'L') next[0] --;

        // 2. 좌표를 벗어난 경우 처리
        if(Math.abs(next[0]) > 5 || Math.abs(next[1]) > 5) {
            next = current.slice(); // next값 되돌림
            continue;
        }

        // 3. 갔던 경로에 저장되어 있는지 확인
        function havePass (current, next) {
            for(let j = 0; j < pass.length; j++) {
                if(pass[j][0].toString() === current.toString() ) {
                    if(pass[j][1].toString() === next.toString()) return true;
                }
                if(pass[j][1].toString() === current.toString() ) {
                    if(pass[j][0].toString() === next.toString()) return true;
                }
            }
        }

        // 갔던 경로에 저장되어 있지 않다면, 경로에 저장
        if(!havePass(current, next)) {
            pass.push([current.slice(), next.slice()]);
        }

        // 현재 위치를 다음 위치로 옮겨줌
        current = next.slice();
    }

    // 가본 경로의 길이 구하기
    return pass.length;
}

 
배열로 중복 체크를 하려니 매우 복잡해졌다.

배열은 참조형 자료이기 때문에, 비교 시 주소값이 비교된다.

배열끼리 비교하려면 toString() 같은 메서드를 이용해서 문자열로 변환해야 한다.

이러한 과정은 코드가 길어지기 때문에 비효율적이다.

통과하긴 했지만 개선이 필요한 코드다.

 

• 정확도 테스트 결과

  

  
   

모범 풀이

function solution(dirs) {

    let move = {'U' : [0,1], 'D' : [0,-1], 'R' : [1,0], 'L' : [-1,0]};
    let current = [0,0]; // 현재 위치
    let pass = new Set(); // 경로 저장할 set 생성

    for(let i = 0; i < dirs.length; i++) {

        let x = current[0] + move[dirs[i]][0]; // 움직일 위치 x 좌표
        let y = current[1] + move[dirs[i]][1]; // 움직일 위치 y 좌표

        if(Math.abs(x) > 5 || Math.abs(y) > 5) continue; // 좌표를 벗어날 경우

        pass.add(''+current[0]+current[1]+x+y); // 경로 추가
        pass.add(''+x+y+current[0]+current[1]);

        current = [x,y]; // 현재 값 갱신
    }

    return pass.size/2; // set의 크기 반환
}

 
힘들게 배열로 값 비교를 할 것이 아니라, 자료형을 바꿔주면 됐다.
하다가 아닌 것 같으면 빨리 다른 방법을 찾는게 현명한 것 같다.
문제 해결을 위해서는 틀을 벗어난 다양한 사고가 필요하다.
 

📌포인트

1. 짝을 이루는 자료라고 해서 배열로 저장하는 것이 최선은 아니다.
   위와 같이 [0,0](출발 위치) & [0,1] (도착 위치)를 배열로 저장하면 값 비교가 힘들다.
   이런 경우 필요에 맞춰 0001와 같은 문자열로 저장하는 것도 방법일 수 있다.
    

2. 중복 검사가 필요한 자료는 Set에 저장하자.
   Set은 중복을 허용하지 않기 때문에 중복검사를 따로 할 필요가 없다.
    

• 정확도 테스트 결과

  

  
   

---

참고

after-newmoon.tistory.com