이 문제에서는 로봇이 상하좌우 네 방향으로 한 번에 한 칸씩 움직입니다. 방향은 위('U'), 아래('D'), 왼쪽('L'), 오른쪽('R')이며, 각 방향의 첫 글자로 구성된 문자열이 주어집니다. 로봇의 초기 위치가 (0, 0)일 때, 주어진 문자열대로 이동한 후 로봇의 최종 위치를 출력하는 것이 목표입니다.
문제 이해를 위한 예시
입력 — 'LDRRUL'
출력 — (0, 0)
풀이 과정 —
L (왼쪽) : (0, 0) -> (-1, 0)
D (아래) : (-1, 0) -> (-1, -1)
R (오른쪽): (-1, -1) -> (0, -1)
R (오른쪽): (0, -1) -> (1, -1)
U (위) : (1, -1) -> (1, 0)
L (왼쪽) : (1, 0) -> (0, 0)
여섯 번의 이동이 모두 상쇄되어 로봇은 다시 원점인 (0, 0)으로 돌아옵니다.
해결 접근 방식
이 문제는 x축과 y축 방향의 이동 횟수를 각각 누적하는 방식으로 간단히 해결할 수 있습니다.
- x좌표: 오른쪽(R) 이동 시 값을 증가시키고, 왼쪽(L) 이동 시 값을 감소시킵니다.
- y좌표: 위(U) 이동 시 값을 증가시키고, 아래(D) 이동 시 값을 감소시킵니다.
모든 문자를 순회한 뒤 누적된 (x, y) 값이 곧 로봇의 최종 위치가 됩니다.
구현 예제
다음은 위 접근 방식을 C++로 구현한 프로그램입니다. 참고로 변수를 반드시 0으로 초기화해야 정확한 결과를 얻을 수 있습니다. 초기화하지 않으면 쓰레기 값(garbage value)이 출력될 수 있습니다.
#include <iostream>
#include <string>
using namespace std;
void robotMoved(string move) {
int xAxis = 0, yAxis = 0; // 반드시 0으로 초기화
int l = move.size();
for (int i = 0; i < l; i++) {
if (move[i] == 'U')
yAxis++;
else if (move[i] == 'D')
yAxis--;
else if (move[i] == 'L')
xAxis--;
else if (move[i] == 'R')
xAxis++;
}
cout << "로봇의 최종 위치 : (" << xAxis << ", " << yAxis << ")" << endl;
}
int main() {
string move = "URLLDDRRUDUDDRU";
robotMoved(move);
return 0;
}
실행 결과
로봇의 최종 위치 : (2, -1)
입력 문자열 "URLLDDRRUDUDDRU"를 한 글자씩 추적해 보면, x축으로는 오른쪽 이동이 왼쪽 이동보다 2번 많고, y축으로는 아래 이동이 위 이동보다 1번 많습니다. 따라서 최종 위치는 (2, -1)이 됩니다.
마무리
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 없이 두 개의 정수 변수만 사용하므로 공간 복잡도는 O(1)입니다. 단순하지만 좌표 누적이라는 기본 개념을 잘 보여주는 대표적인 문자열 처리 문제입니다.