[백준/c++] 4889 - 안정적인 문자열

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

4889번: 안정적인 문자열

---

1) 풀이

이 문제는 이전에 풀었던 '4949 - 균형잡힌 세상' 문제의 응용버전이다.

(괄호에 대한 기본적인 접근 방식은 아래 이전 글을 참고해주길 바람)

2021/03/04 - [알고리즘 코테준비/백준] - [백준/c++] 4949 - 균형잡힌 세상

4949번 같은 경우에는 괄호들이 짝이 맞는가? 에 대해서만 물었다면

이 문제는 괄호들이 짝이 맞기 위해서는 연산이 몇 번 필요한가? 에 대해 묻고 있다.

 

일단, input 처리에 대해서는 4949번과 동일하게 한 문장씩 읽어 처리해주어야 하고,

- 라는 문자가 나왔을 때 읽는 것을종료하면 되므로 getline을 이용해준다.

getline에 대한 설명도 4949번 글을 참고해주길 바람

 

4949번과 동일하게 여는 괄호 { 의 경우 스택에 바로 저장하고

} 가 들어왔을 때 괄호의 짝이 맞다면 pop을 해주면 된다.

이것은 괄호의 짝이 맞는 경우이기 때문에 바로 pop 해주면 됨

 

조금 다르게 처리해주어야 하는 건 닫는 괄호 } 의 경우이다!

짝이 맞지 않는 괄호들을 고치는 연산을 세어주기 위해서는

어떤 괄호가, 어떤 순서로 배치되어있는지 알아야 하기 때문에

1) 스택이 비어있는 경우

2) 스택의 top이 { 가 아니라 } 인 경우

에 닫는 괄호를 스택에 push 해주어야 짝이 맞지 않는 괄호들이

어떻게 배치되어있는지 확인이 가능하다! 

 

한 문장을 다 읽어내고 나면 짝이 맞는 괄호는 이미 스택에 들어있지 않고

짝이 맞지 않는 괄호들만 남아있게 된다.

이때 스택이 비어있다면 연산을 0으로 출력해주고 다음 문장으로

넘어가면 되지만, 아니라면 다음과 같이 처리해준다.

 

연산의 횟수를 카운팅 하는 변수와 현재 스택의 top을 저장하는 변수를 선언한 후 pop한다.

1. top변수와 현재 스택의 top(top변수에 저장한 후 pop한 뒤의 top)이 같은 괄호인 경우

»괄호를 하나만 바꿔주면 짝이 맞게 되므로, 연산 카운팅 변수에 1을 더하고 pop해준다.

 

2. top변수와 현재 스택의 top이 같은 괄호가 아닌 경우

»이미 짝이 맞는 괄호들은 스택에 존재하지 않으므로, 이 경우에는 여는 괄호와 닫는 괄호의 순서가

반대로 되어있는 경우밖에 없다.

»즉, 두개의 괄호 모두 바꿔줘야 하므로 연산 카운팅 변수에 2를 더하고 pop해준다.

 

이 과정을 스택이 비어있지 않는 경우 반복해준 후, 연산 카운팅 변수를 출력하면 된다.

 

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
stack<char>st; //괄호 저장할 스택
string s; 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int v = 1; //output 때 몇번째 문장인지 출력해주는 int 변수
	while (true) {
		getline(cin, s);
		if (s[0] == '-') break; // - 가 하나라도 들어올 경우 종료
		
		for (auto c : s) {
			if (c=='{') {
					st.push(c);	
			}
			else if (c == '}') {
				if (st.empty()||st.top()=='}') {
					st.push(c);
				}
				else if (st.top() == '{') {
					st.pop();
				}

			}
			
		}
		if (st.empty()) {
			cout << v << ". " << 0 << '\n';
			v++;
			continue;
		}
		else {
			int cnt = 0;
			while (!st.empty()) {
				char top = st.top();
				st.pop();
				if (top == st.top()) {
					cnt += 1;
					st.pop();
				}
				else if (top != st.top()) {
					cnt += 2;
					st.pop();
				}
			}
			cout << v << ". " << cnt << '\n';
			v++;
		}
	}
}

3) 참고자료