문제 개요
삼항식(ternary expression)을 담고 있는 문자열이 주어졌을 때, 이 식의 최종 결과를 평가하는 것이 목표입니다. 식은 참(True)과 거짓(False)을 나타내는 T, F와 함께 물음표 ?와 콜론 : 문자로 구성됩니다.
이 문제에는 다음과 같은 제약 조건이 적용됩니다.
- 주어진 문자열의 길이는 10,000 이하여야 합니다.
- 조건식은 오른쪽에서 왼쪽(right-to-left)으로 묶여 평가됩니다.
- 조건 부분은 항상 T 또는 F이며, 숫자 등 다른 값이 올 수 없습니다.
- 식의 최종 결과 역시 항상 T 또는 F입니다.
예를 들어 입력이 "T ? T ? F : T : T"라면, 중첩된 삼항 연산이 오른쪽부터 차례로 처리되어 최종 출력은 F가 됩니다.
해결 접근 방법
문자열을 뒤에서 앞으로 순회하면서 스택(stack)을 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 빈 문자열 ret을 준비하고, n을 문자열 s의 길이로 설정합니다.
- 스택 st를 하나 생성합니다.
- i를 n−1부터 0까지 거꾸로 순회합니다.
- x := s[i]
- 스택이 비어 있지 않고 스택의 맨 위(top)가
?라면 다음을 수행합니다.?를 스택에서 제거(pop)합니다.- first := 현재 스택의 top 값을 저장한 뒤, 두 개의 요소를 제거합니다.
- second := 다시 스택의 top 값을 저장하고 제거합니다.
- x가 T이면 first를, 그렇지 않으면 second를 스택에 넣습니다(push).
- 그 외의 경우에는 x를 그대로 스택에 넣습니다.
- 스택이 빌 때까지 top 값을 ret에 더하면서 제거합니다.
- 마지막으로 ret을 뒤집어 반환합니다.
각 문자를 한 번씩만 처리하기 때문에 시간 복잡도는 O(n), 공간 복잡도도 O(n)으로 매우 효율적입니다.
구현 예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack<char> st;
for(int i = n - 1; i >= 0; i--){
char x = s[i];
if(!st.empty() && st.top() == '?'){
st.pop();
char first = st.top();
st.pop();
st.pop();
char second = st.top();
st.pop();
if(x == 'T'){
st.push(first);
}
else st.push(second);
}
else{
st.push(x);
}
}
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
int main(){
Solution ob;
cout << (ob.parseTernary("T?T?F:T:T"));
}
입력
"T?T?F:T:T"
출력
F
위 코드는 문자열 끝에서부터 시작해 ?를 만날 때마다 조건값에 따라 두 분기 중 하나만 남기는 방식으로 동작합니다. 삼항 연산이 아무리 깊게 중첩되어도 스택 하나만으로 선형 시간 안에 결과를 계산할 수 있다는 점이 이 접근법의 핵심입니다.