[LeetCode] 818. Race Car

출처: https://leetcode.com/problems/race-car/

Race Car - LeetCode

문제

한 차가 무한한 숫자 라인 위에 0에 위치해있고 속도 +1로 달리고 있다. 차는 음수 위치에 갈 수도 있다. 차는 명령어 A와 R의 순서에 따라 자동적으로 운전된다.

• 명령어 A가 주어지면, 차는 다음을 따른다:
  • position += speed
  • speed *= 2

• 명령어 R이 주어지면, 차는 다음을 따른다:
  • 만약 속도가 양수 라면, speed = -1
  • 반대라면, speed = +1
  • 위치는 그대로이다.

 

예를 들어, 명령 AAR 이후, 차의 위치는 0 --> 1 --> 3 --> 3 이고 속도는 1 --> 2 --> 4 --> -1이다.

 

목표 위치 target이 주어지면, 목표 위치에 도달할 수 있는 가장 짧은 명령의 길이 를 반환하라.

예제

Input: target = 3
Output: 2

Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0 --> 1 --> 3.

Input: target = 6
Output: 5

Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.

풀이

문제를 보고 처음 떠올린 생각은 BFS 였습니다.

// [pos, speed, num of instructions]
let queue = [[0, 1, 0]]

while(queue.length) {
    const [pos, speed, ins] = queue.shift();
    if (pos == target) return ins;

    // 'A'
    queue.push([pos+speed, speed*2, ins+1])

    // 'R'
    queue.push([pos, speed > 0 ? -1 : 1, ins+1])
}

이 코드로는 주어진 시간 안에 답을 찾지 못하는데, 이유는 R 명령이 위치는 그대로인 채 속도만 변하는 명령이기 때문입니다. A 명령으로 이동한 모든 위치에서 속도만 바뀌어 큐에 다시 들어갔다 나왔다를 반복하기 때문에 TLE 상황과 직면하게 되는 것입니다.

 

이러한 문제 때문에 R명령을 특정 상황에서만 사용해야 된다는 생각을 했고, 그 상황은 다음과 같습니다.

• pos + speed > target && speed > 0
• pos + speed < target && speed < 0

 

두 상황의 공통점은 목표 지점(Target)을 지나쳐 멀어지는 움직임이라는 것입니다.

 

기본적으로 목표지점 근처까지는 A명령을 통해서 빠르게 움직이고, 목표지점 근방에 도착했을 때, R명령을 통해서 속도 조절을 하겠다는 것입니다. 전체적인 알고리즘이 BFS를 따르기 때문에 이렇게 찾아지는 명령어 수가 찾을 수 있는 가장 작은 명령 수일 거라 생각할 수 있고, 실제 올바른 답을 제 시간 안에 찾을 수 있었습니다.

 

코드의 모습은 같습니다.

// [pos, speed, num of instructions]
let queue = [[0, 1, 0]]

while(queue.length) {
    const [pos, speed, ins] = queue.shift();
    if (pos == target) return ins;

    // 'A'
    queue.push([pos+speed, speed*2, ins+1])

    // 'R'
    if (pos+speed > target && speed > 0 || pos+speed < target && speed < 0) {
        queue.push([pos, speed > 0 ? -1 : 1, ins+1])
    }
}

Github: 818.js