[LeetCode] - 657. Robot Return to Origin
LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Robot Return to Origin" 문제입니다.
--> https://leetcode.com/problems/robot-return-to-origin/description/
문제 :
There is a robot starting at the position (0, 0), the origin, on a 2D plane.
Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.
You are given a string moves that represents the move sequence of the robot where moves[i] represents its ith move. Valid moves are 'R' (right), 'L' (left), 'U' (up), and 'D' (down).
Return true if the robot returns to the origin after it finishes all of its moves, or false otherwise.
Note :
The way that the robot is "facing" is irrelevant. 'R' will always make the robot move to the right once, 'L' will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.
Example 1 :
Input : moves = "UD"
Output : true
Explanation : The robot moves up once, and then down once.
All moves have the same magnitude, so it ended up at the origin where it started.
Therefore, we return true.
Example 2 :
Input : moves = "LL"
Output : false
Explanation : The robot moves left twice.
It ends up two "moves" to the left of the origin.
We return false because it is not at the origin at the end of its moves.
Constraints :
- 1 <= moves.length <= 2 * 10^4
- moves only contains the characters 'U', 'D', 'L' and 'R'.
이 문제에서는 2D 평면에서 로봇이 (0, 0) 위치에서 시작하여 주어진 이동 명령에 따라 움직입니다. 주어진 문자열 moves는 로봇의 이동 경로를 나타냅니다. moves[i]는 i번째 이동을 의미하며, 유효한 이동 명령은 다음과 같습니다 :
- 'R' : 오른쪽으로 한 칸 이동
- 'L' : 왼쪽으로 한 칸 이동
- 'U' : 위쪽으로 한 칸 이동
- 'D' : 아래쪽으로 한 칸 이동
로봇이 모든 이동을 마친 후에 다시 (0, 0)으로 돌아오는지 여부를 판단하는 문제입니다.
// class Solution {
// public boolean judgeCircle(String moves) {
// Stack<Character> stack = new Stack<>();
// for (char move : moves.toCharArray()) {
// if (!stack.isEmpty()) {
// char top = stack.peek();
// if ((move == 'R' && top == 'L') ||
// (move == 'L' && top == 'R') ||
// (move == 'U' && top == 'D') ||
// (move == 'D' && top == 'U')) {
// stack.pop();
// } else {
// stack.push(move);
// }
// } else {
// stack.push(move);
// }
// }
// return stack.isEmpty();
// }
// }
// 초기 생각이지만, 모든 테스트들을 패스하진 못함
// 두번째 아이디어는 더 간단 : 위로 올라가면 ++ 아래로 가면 --, 왼쪽으로 가면 --, 오른쪽으로 가면 ++
public class Solution {
public boolean judgeCircle(String moves) {
int horizontal = 0;
int vertical = 0;
for (int i = 0; i < moves.length(); i++) {
char c = moves.charAt(i);
if (c == 'U') {
vertical++;
} else if (c == 'D') {
vertical--;
} else if (c == 'R') {
horizontal++;
} else if (c == 'L') {
horizontal--;
} else {
return false;
}
}
return horizontal == 0 && vertical == 0;
}
}
첫 코드는 정말 초기 단계에 이게 스택을 써서 풀어야 하는 코드인가 싶어서 써봤는데, 모든 테스트들을 통과하진 못 해서 아이디어를 더 단순하게 바꿔서 했습니다.
이 코드는 문자열 moves를 사용하여 로봇이 모든 이동을 수행한 후 시작점 (0, 0)으로 돌아오는지 판단하는 프로그램입니다. 로봇의 이동은 'U', 'D', 'L', 'R' 문자로 나타내며, 각각 위, 아래, 왼쪽, 오른쪽 이동을 의미합니다.
- 변수 초기화 :
- int horizontal = 0;와 int vertical = 0;는 각각 수평 및 수직 방향의 이동을 추적하는 변수입니다.
- 초기값을 0으로 설정하여 로봇의 시작 위치가 원점 (0, 0)임을 나타냅니다.
- 문자열 순회 :
- moves 문자열을 순회하면서 각 문자에 따라 로봇의 위치를 업데이트합니다.
- char c = moves.charAt(i);로 현재 위치의 문자를 가져옵니다.
- 이동에 따른 위치 업데이트 :
- 각 문자는 로봇의 위치에 영향을 미치며, 이는 다음과 같이 처리됩니다:
- 'U' (Up) : vertical을 증가시켜 위로 이동합니다.
- 'D' (Down) : vertical을 감소시켜 아래로 이동합니다.
- 'R' (Right) : horizontal을 증가시켜 오른쪽으로 이동합니다.
- 'L' (Left) : horizontal을 감소시켜 왼쪽으로 이동합니다.
- 이동 명령 외의 문자가 입력된 경우 return false;로 잘못된 입력임을 알립니다. 하지만, 주어진 문제 조건에 따르면 이 부분은 불필요합니다.
- 각 문자는 로봇의 위치에 영향을 미치며, 이는 다음과 같이 처리됩니다:
- 시작점으로 돌아왔는지 확인 :
- 모든 이동이 완료된 후, horizontal과 vertical이 둘 다 0인지 확인합니다.
- 이 조건이 참이면 로봇이 시작점으로 돌아온 것이며, 따라서 true를 반환합니다.
시간 복잡도
- O(n) : 여기서 n은 moves 문자열의 길이입니다.
- 문자열의 각 문자를 한 번씩 순회하면서 처리하므로, 시간 복잡도는 O(n)입니다.
공간 복잡도
- O(1) : 추가적인 데이터 구조를 사용하지 않으므로 상수 공간 복잡도를 가집니다.
- horizontal과 vertical 두 개의 변수만을 사용하므로 메모리 사용은 일정합니다.
장점 및 한계
장점
- 효율성 : O(n) 시간 복잡도로 문자열을 한 번만 순회하여 문제를 해결합니다.
- 간결성 : 코드가 간단하고 이해하기 쉬우며, 문제의 요구사항을 직접적으로 해결합니다.
한계
- 입력 유효성 검사 : 주어진 문제 조건에 따라 'U', 'D', 'L', 'R' 외의 문자는 없으므로, 해당 조건은 불필요할 수 있습니다. 이 부분을 삭제하여 코드를 단순화할 수 있습니다.
그래서 코드를 조금 더 간결하게 개선 시켜봤습니다 :
public class Solution {
public boolean judgeCircle(String moves) {
int horizontal = 0;
int vertical = 0;
for (char move : moves.toCharArray()) {
if (move == 'R') {
horizontal++;
} else if (move == 'L') {
horizontal--;
} else if (move == 'U') {
vertical++;
} else if (move == 'D') {
vertical--;
}
}
return horizontal == 0 && vertical == 0;
}
}
for (int i = 0; i... )식으로 하는 거보다 for each 방식으로 하는 게 더 나았고, 굳이 else를 할 필요 없이 바로
return horizontal == 0 && vertical == 0으로 해도 되어서 더 효율적인 퍼포먼스를 보이게끔 바꿨습니다.
