백준 10799 c++ " 쇠막대기" -PlusUltraCode-

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

[필자 사고]

스택을 이용해서 짝궁을 찾는 문제다.

처음에 스택 아이디어는 바로 떠올릴수 있었다. 

그러나 해당 막대기 위치를 어떻게 해야 될지 고민했는데 

괄호 짝궁을 만나는 그 순간의 인덱스를 따로 배열에 저장해 놓고 

레이저 괄호 idx와 막대기 괄호 idx의 범위를 이용하여 카운트 하면 해당 문제를 타파할 수 있다.

 

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

[코드 해설]

전체 목적

이 프로그램은 괄호 문자열을 분석하여 다음 두 가지 정보를 추출하고 그에 기반해 결과를 계산합니다:

1. 레이저 (() 형태) 와
2. 막대기 (( ... ) 형태, 레이저가 아닌 닫는 괄호와 짝을 이루는 열리는 괄호)

레이저는 ()처럼 인접한 괄호이고, 막대기는 그 외의 짝이 맞는 괄호쌍입니다.
레이저는 막대기를 자릅니다.
그래서 막대기 안에 있는 레이저 수만큼 막대기가 잘리므로, 잘린 조각 수를 계산하려는 구조입니다.

---

Input() 함수

• 문자열을 입력받아 str 변수에 저장합니다.

---

pushStack(Node nowNode) 함수

괄호의 인덱스와 문자를 쌍으로 받아 처리합니다.
목적: 괄호쌍 분석 및 레이저/막대기 구분.

1. 스택이 비어있으면 현재 노드를 스택에 넣고 종료.
2. 현재 문자가 '('이면 새로운 괄호 열림 → 스택에 push.
3. 현재 문자가 ')'이고, 바로 앞 인덱스가 '('이면 → 레이저로 판단 → 스택에서 pop → raizer 벡터에 저장.
4. 현재 문자가 ')'이고, 앞 인덱스가 바로 연결되지 않은 '('이면 → 막대기의 끝으로 판단 → 스택에서 pop → arr 벡터에 저장.

---

Game_Start() 함수

실제 계산이 이루어지는 함수입니다.

1. 입력 문자열을 한 글자씩 순회하면서, 각 괄호와 인덱스를 Node로 만들어 pushStack()에 전달.
2. 모든 괄호 처리 후:
   • 우선 arr에 저장된 막대기 개수만큼 결과 카운트를 증가시킴.
   • 각 막대기 내부에 포함된 레이저 개수를 셈:
     • arr의 각 막대기에 대해, raizer 중 막대기 안에 위치한 레이저를 모두 찾음.
     • 레이저가 잘라낸 조각 수만큼 resultCount 증가.

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
typedef pair<char, int> Node;
typedef pair<int, int> idxNode;
string str;
stack<Node> myStack;
vector<idxNode> arr;
vector<idxNode> raizer;

void Input() {
	cin >> str;
	
}

void pushStack(Node nowNode) {
	if (myStack.empty()) {
		myStack.push(nowNode);
		return;
	}
	
	Node prevNode = myStack.top();

	if (nowNode.first == '(') {
		myStack.push(nowNode);
		return;
	}
	if (nowNode.first == ')' && prevNode.second + 1 == nowNode.second) {
		myStack.pop();
		raizer.push_back({ prevNode.second,nowNode.second });
		return;
	}
	if (nowNode.first == ')' && prevNode.second + 1 != nowNode.second) {
		myStack.pop();
		arr.push_back({ prevNode.second,nowNode.second });
	}
	
}

int resultCount = 0;

void Game_Start() {
	for (int i = 0; i < str.size(); i++) {
		char ch = str[i];
		Node nowNode = { ch,i };
		pushStack(nowNode);
	}
	
	resultCount += arr.size();

	for (int i = 0; i < arr.size(); i++) {
		idxNode nowNode = arr[i];
		for (int k = 0; k < raizer.size(); k++) {
			if (raizer[k].first > nowNode.first && raizer[k].second < nowNode.second) {
				resultCount++;
			}
		}
	}

}

int main(void) {
	Input();
	Game_Start();
	cout << resultCount;
}