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