leetcode - Walking Robot Simulation

로봇이 commands에 있는 숫자만큼 이동합니다.

이동 중 첫 지점과 로봇의 위치의 두 점으로 이루어진 사각형이 생기며, 사각형이 최대일때의 면적을 구하는 문제입니다.

 

아래는 조건입니다.

• 시작 위치는 (0, 0)
• commands에서 -1은 turn right
• commands에서 -2은 turn left
• commands에서 -1, -2를 제외하고는 0이상 9이하만이 존재
• obstacles는 장애물 위치이며, 장애물이 있으면 로봇은 전진하지 못함

 

저의 경우는 아래와 같이 풀었습니다.

 

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:

        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        direction = 0

        # position (x, y)
        position = [0,0]
        res = 0
        obstacle_set = set(map(tuple, obstacles))

        for command in commands:
            if command == -1 :
                direction = (direction + 1) % 4
            elif command == -2:
                direction = (direction - 1) % 4
            else:
                for i in range(command):
                    if (dx[direction] + position[0], dy[direction] + position[1]) not in obstacle_set:
                        position[1] += dy[direction]
                        position[0] += dx[direction]
                        res = max(res, math.pow(position[0], 2) + math.pow(position[1], 2))
        return int(res)

 

일단, 동서남북으로 움직이기 위한 dx, dy 배열을 만들어 줍니다.

direction은 배열의 인덱스로 방향을 의미합니다.

 

그리고 저는 추가로 로봇의 현재 위치를 알기 위해 position 배열을 하나 만들었습니다.

 

그후는 commands를 이터레이션하며 -1, -2일때는 맞게 방향을 설정합니다.

그리고, 그 외 숫자가 나왔을 경우엔 숫자만큼 for문을 통하여 장애물이 있는지 없는지 체크하고 없다면 전진시킵니다.

 

전진 후에는 만들어진 사각형이 최대인지 max함수를 통해 구해줍니다.

 

사실, 여기서 계속 time 초과로 떨어졌었는데요.

그 이유는 위의 obstacle_set = set(map(tuple, obstacles)) 를 안해주었기 때문이였습니다......

 

장애물들을 list가 아닌 imutable한 tuple로 변환 후 set을 통하여 중복제거하여 불필요한 작업을 하지 않도록 해야합니다.

 

감사합니다.