Walking Robot Simulation
MediumArrayHash TableSimulation
Solution
export function robotSim(commands: number[], obstacles: number[][]): number {
const set = new Set(obstacles.map(([x, y]) => `${y},${x}`));
const directions = [
[1, 0],
[0, 1],
[-1, 0],
[0, -1],
];
let answer = 0;
let [cy, cx, cd] = [0, 0, 0];
for (const command of commands) {
if (command < 0) {
cd = (command === -1 ? cd + 1 : cd + 3) % 4;
continue;
}
let move = command;
const [dy, dx] = directions[cd];
while (0 < move && !set.has(`${cy + dy},${cx + dx}`)) {
[cy, cx] = [cy + dy, cx + dx];
move -= 1;
}
answer = Math.max(answer, cy ** 2 + cx ** 2);
}
return answer;
}
Complexity
- Time:
O(N)
- command에서 최대 움직일 수 있는 최대 거리는
10
이기 때문에 이에 대한 고려를 하지 않아도 된다.
- command에서 최대 움직일 수 있는 최대 거리는
- Space:
O(K)
K
는obstacles
의 크기