https://www.acmicpc.net/problem/4889
여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.
{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.
문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.
입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.
입력의 마지막 줄은 '-'가 한 개 이상 주어진다.
각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.
}{
{}{}{}
{{{}
---
1. 2
2. 0
3. 1
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string Str;
int caseNum = 1;
while(1){
cin >> Str;
if(Str[0] == '-'){
break;
}
int result = 0;
stack<char> stk;
for(auto i : Str){
if(i == '}' && !stk.empty() && stk.top() == '{'){
stk.pop();
} else {
stk.push(i);
}
}
while(!stk.empty()){
char first = stk.top();
stk.pop();
char second = stk.top();
stk.pop();
if(first == second) result++;
else result += 2;
}
cout << caseNum << ". " << result << '\n';
caseNum++;
}
return 0;
}
생각보다 참 간단하게 풀리던 문제.
사실 꽤 오래전, 같은 문제를 못 풀었던 경험이 있다.
중요한 로직은 다음과 같다.
1. 일단 가능한 모든 안정적인 문자열들을 날려버린다.
2. 남아있는 문자열들에 대해 최소한의 계산 량을 카운트한다.
첫 번째 로직부터 살펴보자.
cin >> Str;
if(Str[0] == '-'){
break;
}
int result = 0;
stack<char> stk;
for(auto i : Str){
if(i == '}' && !stk.empty() && stk.top() == '{'){
stk.pop();
} else {
stk.push(i);
}
}
우선 입력받은 데이터에 대해 스택을 활용하여 당장 가능한 안정적인 문자열들을 모두 날린다.
단, 그렇다고 해서 매번 데이터 하나하나를 검토하는 과정에서 처음부터 문자열을 뒤질 필요는 없다.
당장 문자열을 순서대로 읽으며, 그 시점에서 당장 안정적인 문자열 하나를 날릴 수 있는지를 확인하는 것이다.
while(!stk.empty()){
char first = stk.top();
stk.pop();
char second = stk.top();
stk.pop();
if(first == second) result++;
else result += 2;
}
그 후 스택에 남아있는 데이터들을 하나하나 꺼내서 안정적인 문자열로 만들어주면 끝.
어떤 순서로 문제를 해결하는 지에 초점을 두어야 했던 문제였다.