Judge Route Circle

Algorithm
algorithm, leetcode

leetcode 문제링크

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:

  • Input: “UD”
  • Output: true

Example 2:

  • Input: “LL”
  • Output: false

나의 풀이

문제 자체를 이해하기가 좀 어려웠다. 괜히 Circle이라 그래서 왜 원이 되지?라고 생각했는데, 그림을 그려보면 이해하기 쉬웠다. 예를들면 “RLUURDDLU”를 좌표 (0, 0)에서 시작한다고 생각해서 방향따라 그려보면 결국 다시 (0, 0)의 위치로 오게 된다. 이 경우 로봇이 원을 만든다고 가정하여 true를 반환하면 된다. 그래서 “LDRRLRUULR”의 경우 그려보면 (0, 0)의 위치로 돌아오지 않기 때문에 false를 반환하면 된다.

정규식을 이용했다. R과 L의 수와 U와 D의 수가 같으면 원 위치로 되돌아갔다고 할 수 있으니까 다음과 같이 접근해서 풀어보았다.
|| []이 부분은 마지막에 length로 구하고 싶은데 match 메소드가 정규식에 부합하는 문자열이 있으면 배열 형태로 반환하지만 없을 경우 null로 반환하기 때문에 정규식에 일치하는 문자가 없을 경우는 빈배열이 담기도록 하기 위해 추가했다.

1
2
3
4
5
6
7
8
// 68ms
var judgeCircle = function(moves) {
  const R = moves.match(/R/g) || [];
  const L = moves.match(/L/g) || [];
  const U = moves.match(/U/g) || [];
  const D = moves.match(/D/g) || [];
  return R.length === L.length && U.length === D.length
};

이번에는 for문을 통해 문자열을 하나씩 탐색해서 x와 y의 값에 변화를 주는 방법을 사용했다. 오른쪽으로 이동하면 x좌표가 1추가되고 왼쪽으로 이동하면 x좌표가 1 감소하는 것이라 모든 문자열을 탐색한 뒤에 x와 y의 좌표가 다시 0이 되었는지 확인한다.

1
2
3
4
5
6
7
8
9
10
11
12
// 72ms
var judgeCircle = function(moves) {
    let x = 0;
    let y = 0;
    for (const i of moves) {
        i === 'R' ? x++ : 
        i === 'L' ? x-- :
        i === 'U' ? y-- :
        i === 'D' && y++;
    }
    return x === 0 && y === 0
};

같은 접근법인데 reduce 메소드를 이용해 본 방법

1
2
3
4
5
6
7
// 72ms
var judgeCircle = function(moves) {
    const arr = moves.split('');
    const hor = arr.reduce((acc, item) => acc + (item === 'R' ? 1 : item === 'L' ? -1 : 0), 0);
    const ver = arr.reduce((acc, item) => acc + (item === 'U' ? 1 : item === 'D' ? -1 : 0), 0);
    return !(hor + ver)
};

다른 사람 풀이

같은 접근법인데 60ms이길래 환경이 달라서 그런 것 같아서 내가 다시 넣고 돌려보니 72ms가 걸렸다. 각 변수로 x, y를 넣는 대신 배열로 두고 switch 문을 사용한 방법이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 72ms
var judgeCircle = function(moves) {
    var origin = [0,0]
    for(var i = 0; i < moves.length; i++){
        switch(moves[i]){
            case 'U':
                origin[0]++
                break
            case 'D':
                origin[0]--
                break
            case 'L':
                origin[1]--
                break
            case 'R':
                origin[1]++
                break
        }
    }
    if(origin[0] == 0 && origin[1] == 0){
        return true
    }else{
        return false
    }
};

문제의 좋아요와 싫어요 수가 거의 비슷해서 왜 인가했는데, 문제 자체가 이해가 어려워서였던 것 같다. 괜히 원을 만든다는 가정이 문제를 이해하기 어렵게 했다. 근데 문제 자체를 이해하고 나니 풀이는 재미있었다.
특히 match메소드를 이용해서 null이 나오는데 배열의 length 프로퍼티로 비교하려고 하려면 어떻게 처리해야할까 고민했는데, || 논리 연산자를 이용해 match 메소드에서 null이 나오면 변수에 빈배열이 대입되도록 처리했다. 두번째 풀이의 삼항연산자에 쓴 것과 같이 &&와 ||같은 논리 연산자의 특성을 활용해보니 코드가 굉장히 깔끔해보여서 기분이 좋았다.

Share Comments