[BOJ S1][C++] 백준 4889번 : 안정적인 문자열

https://www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

 

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

 

풀이

스택을 이용하여 괄호들의 짝을 맞추면 (아래 문제 풀이 참고, 이때 짝이 안맞을 경우에도 리턴하지 않고 연산을 이어나간다)

[🐕 Baaaaaarking/0x08강 - 스택의 활용 (수식의 괄호쌍)] - [BOJ S4][C++] 백준 9012번: 괄호

[BOJ S4][C++] 백준 9012번: 괄호

연산 후 스택에는 짝이 맞지 않는 괄호들만 남는다.

이 스택에서 두개씩 꺼내서 (개수는 무조건 짝수이므로)

 

1. 두 괄호의 방향이 같다면 ans++ ( '{{',  '}}' )
2.두 괄호의 방향이 다르다면 ans+2 ( '}{' )

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <stack>

using namespace std;
    
int main() {
    string input;
    
    int case_num = 1;
    
    while(getline(cin, input)) {
        if(input[0]=='-') {
            break;
        }
        
        stack<char> s;
        for(int i=0; i<input.size(); i++) {
            if(input[i] == '}' && !s.empty() && s.top() == '{')
                s.pop();
            else
                s.push(input[i]);
        }

        int ans = 0;
        while(!s.empty()) {
            char first = s.top();
            s.pop();
            char second = s.top();
            s.pop();
            
            if(first == second) ans++;
            else ans += 2;
        }
        
        cout <<  case_num << ". " << ans << "\n";
        case_num++;
    }
    
    return 0;
}

/*
 */

 

solution() 코드 버전 (프로그래머스)

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <stack>

using namespace std;

int solution(stack<char> &s) {
    int ans = 0;
    while(!s.empty()) {
        char first = s.top();
        s.pop();
        char second = s.top();
        s.pop();
        
        if(first == second) ans++;
        else ans += 2;
    }
    return ans;
}

stack<char> bracket_stack(string &input) {
    stack<char> s;
    
    for(int i=0; i<input.size(); i++) {
        if(input[i] == '}' && !s.empty() && s.top() == '{')
            s.pop();
        else
            s.push(input[i]);
    }
    
    return s;
}

int main() {
    string input;
    
    int case_num = 1;
    
    while(getline(cin, input)) {
        if(input[0]=='-') {
            break;
        }

        stack<char> s = bracket_stack(input);
        int ans = solution(s);
        
        cout <<  case_num << ". " << ans << "\n";
        case_num++;
    }
    
    return 0;
}

/*
 */