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

문제 출처

프로그래머스 lev2 - 방문길이

나의 풀이

1차 시도(실패)

function solution(dirs) {
  const d = [[0,1], [0,-1], [1,0], [-1,0]];
  const dir = { 'U': d[0], 'D': d[1], 'R': d[2], 'L': d[3] };
  let len = [[dir[dirs[0]][0], dir[dirs[0]][1]]];

  for (let i=1; i<dirs.length; i++) {
    let mv = [dir[dirs[i]][0], dir[dirs[i]][1]];
    let moving = [len[len.length-1][0]+mv[0], len[len.length-1][1]+mv[1]]
    if (Math.abs(moving[0]) <= 5 && Math.abs(moving[1]) <= 5) {
      len.push(moving);
    }
  }
  
  len = [...new Set(len.join('|').split('|'))].map((v) => v.split(',')).map((v) => v.map((a) => +a));

  return len.length+1;
}

console.log(solution("ULURRDLLU"));
// console.log(solution("LULLLLLLU"));

2차 시도(35/100)

function solution(dirs) {
  const d = [[0,1], [0,-1], [1,0], [-1,0]];
  const dir = { 'U': d[0], 'D': d[1], 'R': d[2], 'L': d[3] };
  const len = [[0,0], [dir[dirs[0]][0], dir[dirs[0]][1]]];
  let answer = [];


  for (let i=1; i<dirs.length; i++) {
    let mv = [dir[dirs[i]][0], dir[dirs[i]][1]];
    let moving = [len[len.length-1][0]+mv[0], len[len.length-1][1]+mv[1]]
    if (Math.abs(moving[0]) <= 5 && Math.abs(moving[1]) <= 5) {
      answer.push([...len[len.length-1], ...moving]);
      len.push(moving);
    }
  }

  answer = [...new Set(answer.join('|').split('|'))].map((v) => v.split(',')).map((v) => v.map((a) => +a));
  return answer.length+1;
}

console.log(solution("ULURRDLLU"));
// console.log(solution("LULLLLLLU"));

3차 시도(통과)

효율적이지 않은 풀이인 건 분명하다.

// 1.
for문을 순회하면서 이동 좌표를 추적한다.
이때 이동 전 좌표와, 이동 후 좌표를 하나의 요소로 묶은 answer 배열도 같이 채워나간다.

// 2.
중첩 배열의 중복을 제거해준다.

// 3.
반례("LRLRL")의 경우, [ [ -1, 0, 0, 0 ], [ 0, 0, -1, 0 ] ] 가 되는데, 얘네 둘도 중복으로 처리해야 한다.

왜냐하면, 거리 개념이므로 (-1,0) => (0,0) 로의 이동 뿐만 아니라 (0,0) => (-1,0)으로의 이동도 거리 관점에서는 중복이기 때문이다.

new Set()으로 중복을 제거해주는데,
배열 중복 제거가 목적이라면, 문자열로 변환해서 add 해주면 된다.

function solution(dirs) {
  const d = [[0,1], [0,-1], [1,0], [-1,0]];
  const dir = { 'U': d[0], 'D': d[1], 'R': d[2], 'L': d[3] };
  const len = [[0,0]];
  let answer = [];

// 1.
  for (let i=0; i<dirs.length; i++) {
    let mv = [dir[dirs[i]][0], dir[dirs[i]][1]];
    let moving = [len[len.length-1][0]+mv[0], len[len.length-1][1]+mv[1]]
    if (Math.abs(moving[0]) <= 5 && Math.abs(moving[1]) <= 5) {
      answer.push([...len[len.length-1], ...moving]);
      len.push(moving);
    }
  }
// 2. 
  answer = [...new Set(answer.join('|').split('|'))].map((v) => v.split(',')).map((v) => v.map((a) => +a));
  
// 3. 
    let result = new Set();
  for (let x of answer) {
    // result.add(`${x[0]}${x[1]}${x[2]}${x[3]}`);
    // result.add(`${x[2]}${x[3]}${x[0]}${x[1]}`);
    result.add(`${x.slice(0,2)}${x.slice(2,4)}`);
    result.add(`${x.slice(2,4)}${x.slice(0,2)}`);
    
  }
  
  return result.size/2;
}

// console.log(solution("ULURRDLLU"));
// console.log(solution("LULLLLLLU"));
console.log(solution("LRLRL"));

다른 풀이

현재 위치를 갱신하는 방식

function solution(dirs) {
  let move = { L: [-1, 0], R: [1, 0], U: [0, 1], D: [0, -1] };
  let now = [0, 0];
  let route = new Set();
  
  for (let dir of dirs) {
      let nowX = now[0] + move[dir][0];
      let nowY = now[1] + move[dir][1];
      
      if (nowX > 5 || nowX < -5 || nowY > 5 || nowY < -5) continue;
      
      route.add("" + now[0] + now[1] + nowX + nowY);
      route.add("" + nowX + nowY + now[0] + now[1]);
      
      now = [nowX, nowY];
  }
  
  return route.size / 2;
}

방문 체크

function solution(dirs) {
    let count = 0;

    const moveObj = {
        "U": [0, 1],
        "D": [0, -1],
        "R": [1, 0],
        "L": [-1, 0]
    }

    let pos = [0,0];    // 현재위치
    const visited = [];    // 방문한 좌표 목록

    for(let i = 0, len = dirs.length; i < len; i++) {
        const moveValue = moveObj[dirs[i]];
        const move = [pos[0] + moveValue[0], pos[1] + moveValue[1]];    // 이동할 좌표

          // 좌표평면의 경계를 넘어가는 경우
        if(move[0] > 5 || move[0] < -5 || move[1] > 5 || move[1] < -5) {
            continue;
        }

        const startIndex = (5+pos[0]) + (5-pos[1]) * 11;    // 이동전 좌표
        const endIndex = (5+move[0]) + (5-move[1]) * 11;    // 이동후 좌표

        pos = move;

          // 방문여부 확인
        const isVisited = visited.find((item) => {
            if( (item[0] === startIndex && item[1] === endIndex)
               || (item[0] === endIndex && item[1] === startIndex) ) {
                return true;
            }
        })

        if( !isVisited ) {
            ++count;
            visited.push([startIndex, endIndex]);
        }
    }

    return count;
}

참고

[프로그래머스] 방문 길이 - JavaScript
[프로그래머스/JavaScript] 방문 길이 (Level 2)