문제 개요
n개의 문자로 이루어진 문자열 S가 있다고 가정해 봅시다. 각 문자는 'R' 또는 'U'입니다. 2차원 평면 위의 로봇은 오른쪽 또는 위로만 이동할 수 있으며, 'R'을 만나면 오른쪽으로, 'U'를 만나면 위로 움직입니다.
그런데 문자열이 너무 길다면 이를 더 짧게 압축하는 것이 좋겠죠. 여기서 "RU" 또는 "UR"로 이루어진 연속된 두 문자는 대각선 이동을 의미하는 "D" 하나로 대체됩니다. 우리가 구해야 할 값은 바로 이렇게 압축된 최종 문자열의 길이입니다.
예를 들어 입력이 S = "RUURU"라고 한다면, 출력은 3이 됩니다. 문자열이 "DUD"로 압축되기 때문입니다.
풀이 접근 방법
이 문제는 문자열을 한 번만 순회하면서 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 인접한 두 문자가 서로 다르면(즉, "RU" 또는 "UR") 두 이동을 하나의 대각선 이동 "D"로 합치고, 인덱스를 한 칸 더 건너뜁니다.
- 인접한 두 문자가 같으면 해당 이동을 그대로 하나로 계산합니다.
- 매 단계마다 결과 카운터(ans)를 1씩 증가시킵니다.
알고리즘을 의사 코드로 표현하면 다음과 같습니다.
ans := 0
n := size of S
for initialize i := 0, when i < n, update (increase i by 1), do:
if S[i] is not equal to S[i + 1], then:
(increase i by 1)
(increase ans by 1)
return ans
C++ 구현 예제
아래 예제 코드를 통해 실제 동작을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(string S){
int ans = 0;
int n = S.size();
for (int i = 0; i < n; ++i){
if (S[i] != S[i + 1])
i++;
ans++;
}
return ans;
}
int main(){
string S = "RUURU";
cout << solve(S) << endl;
}
입력
"RUURU"
출력
3
동작 원리 살펴보기
입력 문자열 "RUURU"를 단계별로 추적해 보면 다음과 같습니다.
- i = 0: S[0] = 'R', S[1] = 'U' → 서로 다르므로 "RU"를 "D"로 합치고 i를 추가로 증가 → ans = 1
- i = 2: S[2] = 'U', S[3] = 'R' → 서로 다르므로 "UR"을 "D"로 합침 → ans = 2
- i = 4: S[4] = 'U' → 마지막 문자이므로 그대로 하나로 계산 → ans = 3
따라서 최종 결과는 3이며, 압축된 문자열은 "DUD"가 됩니다.
이 알고리즘의 시간 복잡도는 O(n)이고, 별도의 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 문자열을 한 번만 순회하면 되기 때문에 아주 긴 입력 문자열에도 효율적으로 동작한다는 장점이 있습니다.