백준 4889 안정적인 문자열

작성일 | In |

Problem : 안정적인 문자열

유형 : 스택

문제 , 입출력 설명

링크로 대체합니다

해결 전략

안정적인 문자열을 만들기 위해서는 필수적으로 여는 괄호가 필요하다

빈 상태에서 } 이 나온 경우
반드시 { 로 바꿔주는 작업을 한다.

{ 이 나올 경우, 계속 삽입하고,
} 이 나올 경우, 앞이 { 라면 pop해준다.

마지막에 스택이 비어있지 않다면, 모든 원소가 { 로 차있을 것이다.
항상 짝수 개수의 괄호의 입력이 보장되므로 문제조건
절반만 } 로 바꿔주는 연산을 더 해주면 안정적인 문자열을 만드는것에 성공한다.

주의할 점

  • 없음

풀이

해결전략에 모든 과정을 서술해두었다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

string str;

bool end_check() {
    if (str[0] == '-')  return true;
    else return false;
}

int solve() {
    stack<char> s;
    int oper_cnt = 0;

    for (char bracket : str) {
        if (bracket == '{') s.push(bracket);
        else {
            if (s.empty()) {
                s.push('{');
                oper_cnt++;
            }
            else if (s.top() == '{') s.pop();
        }
    }

    oper_cnt += (int)s.size() / 2;
    return oper_cnt;
}

void input() {
    int cnt = 1;
    while (1) {
        cin >> str;
        if (end_check()) return;
        cout << cnt++ << ". " << solve() << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    input();

    return 0;
}

피드백

없음