문제 설명
'L', 'R', '?' 세 가지 문자로만 이루어진 문자열 s가 주어집니다. 'L'은 왼쪽으로 한 칸 이동, 'R'은 오른쪽으로 한 칸 이동을 의미하며, '?'는 'L' 또는 'R' 중 어느 쪽이든 자유롭게 선택할 수 있는 자리입니다. 위치 0에서 출발할 때, '?'를 적절히 'L' 또는 'R'로 바꿔서 원점(0)에서 도달할 수 있는 최대 거리를 구하는 것이 목표입니다.
예를 들어 입력이 "LLRRL??"라면 출력은 3이 됩니다. 두 개의 '?'를 모두 'L'로 바꾸면 왼쪽으로 5칸, 오른쪽으로 2칸 이동하게 되어 최종 변위는 |5 − 2| = 3입니다.
접근 방법
이 문제의 핵심은 간단한 그리디(greedy) 아이디어입니다. 최대 거리를 만들려면 모든 '?'를 더 많이 등장한 방향과 같은 쪽으로 바꾸면 됩니다. 구체적인 해결 단계는 다음과 같습니다.
- 카운터 변수 op(물음표 개수), l('L' 개수), r('R' 개수)을 0으로 초기화합니다.
- 문자열 s의 각 문자를 순회합니다.
- 문자가 'L'이면 l을 1 증가시킵니다.
- 문자가 'R'이면 r을 1 증가시킵니다.
- 그 외('?'인 경우)에는 op를 1 증가시킵니다.
- max(l, r) − min(l, r) + op를 반환합니다.
왜 이 공식이 성립할까요? l과 r 중 큰 값에서 작은 값을 빼면 이미 확정된 이동들만으로 생기는 순변위가 계산됩니다. 그리고 각 '?'는 항상 더 유리한 쪽(더 많이 이동한 방향)으로 배치할 수 있으므로, 물음표 개수인 op만큼 거리를 추가로 늘릴 수 있기 때문입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(string s) {
int op = 0;
int l = 0;
int r = 0;
for (auto &it : s) {
if (it == 'L') {
l++;
} else if (it == 'R') {
r++;
} else {
op++;
}
}
return max(l, r) - min(l, r) + op;
}
};
main() {
Solution ob;
cout << (ob.solve("LLRRL??"));
}
입력
"LLRRL??"
출력
3
복잡도 분석
시간 복잡도는 문자열을 한 번만 순회하므로 O(n)이며, 추가로 사용하는 변수가 상수 개수뿐이므로 공간 복잡도는 O(1)입니다. 문자열 길이와 무관하게 매우 효율적으로 동작하는 솔루션입니다.