-
[๋ฐฑ์ค(BOJ) 10799๋ฒ] ์ ๋ง๋๊ธฐ (C++)PS(Problem Solving)/C++ 2022. 1. 20. 23:39๋ฐ์ํ
๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/10799
๋ฌธ์ ์ ๋ณด
์ ๋ ฅ
ํ ์ค์ ์ ๋ง๋๊ธฐ์ ๋ ์ด์ ์ ๋ฐฐ์น๋ฅผ ๋ํ๋ด๋ ๊ดํธ ํํ์ด ๊ณต๋ฐฑ์์ด ์ฃผ์ด์ง๋ค. ๊ดํธ ๋ฌธ์์ ๊ฐ์๋ ์ต๋ 100,000์ด๋ค.
์ถ๋ ฅ
์๋ ค์ง ์กฐ๊ฐ์ ์ด ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์๋ฅผ ํ ์ค์ ์ถ๋ ฅํ๋ค.
ํ์ด
์๊ฐ์ด ์ด๋ ค์ ๊ณ ๊ตฌํ์ ์ฌ์ ๋ ๋ฌธ์ ์๋ค. ์ฌ๋ ๊ดํธ๋ ์คํ์ push ํด์ฃผ๊ณ ๋ซ๋ ๊ดํธ์ผ ๋ ๋ฐ๋ก ์์ ๊ดํธ๊ฐ ์ฌ๋ ๊ดํธ์ธ์ง, ๋ซ๋ ๊ดํธ์ธ์ง๋ฅผ ํตํด ๋ ์ด์ ์ ์ ๋ง๋๊ธฐ์ ๋์ ๊ตฌ๋ณํ๋ฉด ๋๋ค.
์์ค ์ฝ๋
#include <bits/stdc++.h> using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); string str; cin >> str; stack<char> S; int ans = 0; for (int i = 0; i < str.length(); i++) { if (str[i] == '(') { // ์ฌ๋ ๊ดํธ S.push(str[i]); } else { // ๋ซ๋ ๊ดํธ if (str[i - 1] == '(') { // ๋ ์ด์ ์ผ ๊ฒฝ์ฐ S.pop(); // ์ ๋ง๋๊ธฐ๋ก ์ฐฉ๊ฐํ๊ณ ์์์ ์คํ์ ์ฌ๋ ๊ดํธ๋ฅผ ํ๋ ์ถ๊ฐํ์ผ๋ฏ๋ก pop ํ๋ค. ans += S.size(); // ์ ๋ง๋๊ธฐ์ ๊ฐ์๋งํผ ์กฐ๊ฐ์ด ์๋ฆฐ๋ค. } else { // ์ ๋ง๋๊ธฐ์ ๋์ผ ๊ฒฝ์ฐ S.pop(); // ๋ง๋๊ฐ ๋๋ฌ์ผ๋ฏ๋ก ๋ง๋๊ธฐ ํ๋ ์ ๊ฑฐ(์ฌ๋ ๊ดํธ ์ ๊ฑฐ) ans++; // ์ ๋ง๋๊ธฐ์ ๋(์ค๋ฅธ์ชฝ) ์กฐ๊ฐ์ ๋ํด์ค๋ค. } } } cout << ans; return 0; }
๋ฐ์ํ