[백준 10799] 쇠막대기 (C++/Python)

C++)

#include <iostream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	string str;
	cin >> str;

	int ans = 0;
	stack<char> st;

	for (int idx = 0; idx < str.length(); idx++) {
		if (str[idx] == '(')
			st.push(str[idx]);
		else {
			st.pop();

			ans += (str[idx - 1] == '(' ? st.size() : 1);
		}
	}

	cout << ans;

	return 0;
}

 

 

 

Python)

import sys

temp = sys.stdin.readline().rstrip()

st = []
ans = 0

for idx, ch in enumerate(temp):
    if ch == '(':
        st.append(ch)
    else:
        st.pop()
        ans += (len(st) if temp[idx-1] == '(' else 1)
print(ans)

 

 

C++이랑 파이썬 코드의 알고리즘은 동일하다.

1. 여는 괄호면 스택에 무조건 넣는다.

2. 닫는 괄호이면 레이저이든 쇠막대기의 끝이든 더이상 스택에 있으면 안되므로 POP한다.

  2.1 단, 닫는 괄호 앞에 여는 괄호가 있었다면 (레이저라면) 기존에 가지고 있었던 쇠막대기들을 전부 자를 수 있는 것이므로 스택 사이즈만큼 더한다.

  2.2 쇠막대기의 끝이라면, 쇠막대기의 끄트머리만 남은 것이므로 1을 더한다.