LeetCode [874]: Walking Robot Simulation

📌 LeetCode [874]: Walking Robot Simulation

🔗 문제 링크

---

문제 설명 📄

로봇이 무한한 XY 평면에서 (0, 0)에서 시작하여 북쪽을 바라보고 있다.
명령과 장애물 배열이 주어졌을 때, 로봇이 이동 중 도달할 수 있는 최대 제곱 거리를 계산하라.

• 명령:
  • -2: 왼쪽으로 90도 회전
  • -1: 오른쪽으로 90도 회전
  • 1 <= k <= 9: k 단위만큼 전진
• 장애물: 특정 위치에 있는 장애물 좌표.

---

문제 접근 방식 🚶

1. 방향 정의:
   • 북, 동, 남, 서 순으로 이동 벡터를 정의.
   • 회전 명령에 따라 방향 인덱스를 갱신.
2. 전진 명령:
   • 장애물이 없는 경우에만 이동.
   • 이동 중 최대 유클리드 거리 제곱 값을 갱신.
3. 장애물 처리:
   • 장애물 좌표를 set으로 변환하여 빠른 조회 가능.

---

Solution 💻

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]] 
        obstacles = set(map(tuple, obstacles))

        point = 0 
        x, y = 0, 0  
        answer = 0

        for command in commands:
            if command == -2: 
                point = (point - 1) % 4
            elif command == -1: 
                point = (point + 1) % 4
            else:  # 전진
                for _ in range(command):
                    next_x = x + direction[point][0]
                    next_y = y + direction[point][1]
                    if (next_x, next_y) in obstacles:  
                        break
                    x = next_x
                    y = next_y
                    answer = max(answer, x**2 + y**2) 

        return answer

---

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n + m)
  • n: 명령의 개수
  • m: 장애물의 개수
  • 각 명령에서 최대 k번의 이동 시도를 할 수 있지만, 장애물 확인은 set을 사용하므로 O(1)로 수행됩니다.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(m)
  • 장애물을 저장하는 set의 공간입니다.