백준 4889 c++ "안정적인 문자열" -PlusUltraCode-

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

 

[필자 사고]

가로 문제 중괄호를 보고 스택 자료구조가 생각이 났다. 

그래서 스택을 이용하여 풀 수 있을까 생각 하다가 다음과 같은 결론에 도달했다.

짝이 있는 괄호들은 제외한다.

짝이 없는 괄호중 열린 괄호의 갯수와 닫힌 괄호의 갯수를 구한다음

괄호의 갯수에 2를 나눠주고 나머지를 더하는 형태로 해당 문제를 풀었다.

 

스택 자료구조와 그리디 알고리즘을 이용하여 쉽게 풀 수 있엇다.

아래는 자세한 코드해설이다.

[코드 해설]

2. 게임 시작 함수 (Game_Start 함수)

Game_Start() 함수는 문자열과 테스트 케이스 번호를 매개변수로 받아 처리한다. 문자열을 처음부터 끝까지 순회하며 {는 스택에 넣고, }를 만났을 때는 endGaro() 함수를 호출해 중괄호 짝이 맞는지를 검사하고 스택을 조정한다. 이후 문자열의 처리가 끝난 후에는 calculateGaro() 함수를 통해 최종적으로 몇 번의 중괄호 변경이 필요한지 계산하고 출력한다.

---

3. 중괄호 짝 검사 (endGaro 함수)

endGaro() 함수는 닫는 중괄호 }를 만났을 때 호출된다. 스택이 비어있으면 짝이 될 여는 괄호가 없기 때문에 해당 닫는 괄호를 스택에 넣는다. 스택이 비어있지 않다면 가장 위의 요소가 여는 괄호 {인지 확인하고, 그렇다면 스택에서 해당 여는 괄호를 제거하여 짝이 맞았음을 의미하게 처리한다. 그렇지 않으면 현재 닫는 괄호를 그대로 스택에 넣는다.

---

4. 괄호 변경 횟수 계산 (calculateGaro 함수)

calculateGaro() 함수는 스택에 남아 있는 괄호들을 기반으로 몇 번의 괄호 방향 변경이 필요한지를 계산한다. 스택에 남은 괄호들을 순회하며 여는 괄호 {의 개수와 닫는 괄호 }의 개수를 각각 센다. 이 두 값을 바탕으로 각 두 쌍마다 1번의 변경이 필요하며, 홀수 개가 남는 경우를 위해 나머지 처리를 포함한다. 즉, (startGaroCount / 2 + startGaroCount % 2)와 (endGaroCount / 2 + endGaroCount % 2)의 합이 총 필요한 괄호 변경 횟수가 된다.

---

5. 메인 함수 (main 함수)

main() 함수는 문자열을 표준 입력으로부터 반복해서 읽는다. 입력된 문자열이 -일 경우 반복을 종료한다. 그 외의 경우 Game_Start() 함수를 호출하여 처리하며, 각 테스트 케이스에 대해 번호를 매긴다.

[소스 코드]

#include <iostream>
#include <stack>
#include <vector>
#include <cstring>

using namespace std;

void endGaro(stack<char>& myStack, char str) {
	if (myStack.empty()) {
		myStack.push(str);
		return;
	}

	char ch = myStack.top();
	if (ch == '{') {
		myStack.pop();
		return;
	}
	else {
		myStack.push(str);
		return;
	}
	
}

int calculateGaro(stack<char>& myStack) {
	int startGaroCount = 0;
	int endGaroCount = 0;
	while (!myStack.empty()) {
		char ch = myStack.top();
		myStack.pop();

		if (ch == '{') {
			startGaroCount++;
		}
		else {
			endGaroCount++;
		}
	}

	int resultCount = 0;
	resultCount = startGaroCount / 2 + startGaroCount % 2 + endGaroCount / 2 + endGaroCount % 2;

	return resultCount;
}


void Game_Start(string str, int testCount) {
	stack<char> myStack;

	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '{') {
			myStack.push(str[i]);
		}
		else {
			endGaro(myStack, str[i]);
		}
	}
	cout << testCount << ". " << calculateGaro(myStack) << '\n';
}

int main(void) {
	string str;
	int testCount = 1;
	while (cin >> str) {
		if (str[0] == '-')break;
		Game_Start(str,testCount++);
	}
}