문제 개요
여는 괄호 '(' , 닫는 괄호 ')' 그리고 영어 소문자로 이루어진 문자열 s가 있다고 가정해 봅시다. 우리는 문자열에서 최소 개수의 괄호를 제거하여 결과 문자열이 유효한(valid) 괄호 문자열이 되도록 만들어야 하며, 가능한 유효한 문자열 중 하나를 반환하면 됩니다.
괄호 문자열이 유효하려면 다음 조건 중 하나를 만족해야 합니다.
빈 문자열이거나, 영어 소문자만으로 구성된 경우
A와 B가 모두 유효한 문자열일 때, 두 문자열을 연결한 AB 형태로 표현할 수 있는 경우
A가 유효한 문자열일 때, (A) 형태로 표현할 수 있는 경우
예를 들어 입력이 "a)b(c)d"라면, 짝이 맞지 않는 닫는 괄호 하나만 제거하면 되므로 출력은 "ab(c)d"가 됩니다.
접근 방법: 스택 활용
이 문제는 스택(stack) 자료구조를 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
여는 괄호 '('를 만나면 해당 위치의 인덱스를 스택에 저장합니다.
닫는 괄호 ')'를 만나면 대응되는 여는 괄호가 있는지 확인합니다. 스택이 비어 있지 않다면 짝이 맞는 것이므로 pop하고, 비어 있다면 이 닫는 괄호는 잘못된 것이므로 '*'로 표시합니다.
모든 문자를 확인한 후에도 스택에 남아 있는 여는 괄호들은 짝이 없는 것이므로 역시 '*'로 표시합니다.
마지막으로 '*'로 표시된 문자들을 제외한 나머지 문자들만 이어 붙여 정답 문자열을 완성합니다.
알고리즘 단계
- 정수형 스택 st를 정의합니다.
- i를 0부터 s의 길이까지 순회하며 다음을 수행합니다.
- s[i]가 '('이면 인덱스 i를 스택에 삽입(push)합니다.
- s[i]가 ')'라면, 스택이 비어 있지 않으면 pop하고, 비어 있으면 s[i] = '*'로 표시합니다.
- 스택이 빌 때까지 스택의 top 위치에 해당하는 문자를 '*'로 바꾸고 pop합니다.
- 빈 문자열 ans를 선언합니다.
- i를 0부터 s의 길이 - 1까지 순회하며, s[i]가 '*'가 아니면 ans에 해당 문자를 추가합니다.
- ans를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack <int> st;
for(int i = 0; i < s.size(); i++){
if(s[i] == '(')st.push(i);
else if(s[i] == ')'){
if(!st.empty())st.pop();
else s[i] = '*';
}
}
while(!st.empty()){
s[st.top()] = '*';
st.pop();
}
string ans = "";
for(int i = 0; i < s.size(); i++){
if(s[i] != '*')ans += s[i];
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}
실행 결과
입력
"a)b(c)d"
출력
ab(c)d
복잡도 분석
이 알고리즘은 문자열을 최대 세 번 순회하므로 시간 복잡도는 O(n)입니다. 또한 스택에는 최대 n개의 인덱스가 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다. 스택을 활용하면 어떤 괄호가 짝이 맞지 않는지 직관적으로 판별할 수 있어, 최소 제거 문제를 간결하게 해결할 수 있습니다.