[Hard] 818. Race Car (Java)

https://leetcode.com/problems/race-car/description/

Race Car - LeetCode

DP로 풀걸,,

---

※  Question Summary

▶ Your car starts at position 0 and speed +1 on an infinite number line (also can go into negative positions)

▶ There are only two modes to drive. 'A' (accelerate) and 'R' (reverse)

• 'A'
  
  • position += speed
  • speed *= 2
• 'R'
  
  • If your speed is positive then speed = -1
  • otherwise speed = 1
  • Your postion stays the same

▶ Given a target position 'target', return the length of the shortest seqeunce of instructions to get there

For example, after commands "AAR", 
your car goes to positions 0 --> 1 --> 3 --> 3, and
 your speed goes to 1 --> 2 --> 4 --> -1.

---

◈ Constraints

• 1 <= target <= 10^4

---

◈ Input - 1

target = 3

◈ Output - 1

2

◈ Input - 2

Input: target = 6

◈ Output - 2

5

---

 ◎  Solution

▶ Create the class 'Car' which has the speed, position, count of sequence

▶ Override the equals, hashcode to enablle the use of hashSet

▶ We can use BFS since it can be respresented as a node

▶ Check if it has been visited using the hashset and whether the position exceeds twice the target value

---

 

class Car {
    int m_nSpeed;
    int m_nPosition;
    int m_nCount;

    Car(int nSpeed, int nPosition, int nCount) {
        m_nSpeed = nSpeed;
        m_nPosition = nPosition;
        m_nCount = nCount;
    }

    @Override
	public boolean equals(Object o) {
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;
		Car car = (Car) o;
		return m_nSpeed == car.m_nSpeed && m_nPosition == car.m_nPosition;
	}

   @Override
    public int hashCode() {
        return Objects.hash(m_nSpeed, m_nPosition);
    }
}

class Solution {
    public int racecar(int target) {
        HashSet<Car> visit = new HashSet<>();
        Queue<Car> BFS = new LinkedList<>();

        BFS.add(new Car(1, 0, 0));
        visit.add(new Car(1, 0, 0));
        while(!BFS.isEmpty()) {
            Car car = BFS.poll();

            if(car.m_nPosition == target)
                return car.m_nCount;

            // accelerate
            Car A = accelerate(car);
            if(!visit.contains(A) && isValid(A, target)) {
                visit.add(A);
                BFS.add(new Car(A.m_nSpeed, A.m_nPosition, car.m_nCount+1));
            } 

            // reverse
            int nSpeed = reverse(car.m_nSpeed);
            Car R = new Car(nSpeed, car.m_nPosition, car.m_nCount+1);
            if(!visit.contains(R) && isValid(R, target)) {
                visit.add(R);
                BFS.add(R);
            }
        }

        return 0;
    }

    public int reverse(int nSpeed) {
        if(nSpeed >= 0)
            return -1;
        return 1;
    }

    public Car accelerate(Car car) {
        int nPosition = car.m_nPosition + car.m_nSpeed;
        int nSpeed = car.m_nSpeed * 2;

        return new Car(nSpeed, nPosition, 0);  
    }

     public boolean isValid(Car car, int target) {
        if (Math.abs(car.m_nPosition) > 2 * target) {
            return false;
        }

        return true;
    }
}

---

 

I HOPE YOUR DAY GOES WELL :)