๋ฌธ์
4๊ฐ์ ๊ธฐํธ ‘(’, ‘)’, ‘[’, ‘]’๋ฅผ ์ด์ฉํด์ ๋ง๋ค์ด์ง๋ ๊ดํธ์ด ์ค์์ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด์ด๋ ๋ค์๊ณผ ๊ฐ์ด ์ ์๋๋ค.
- ํ ์์ ๊ดํธ๋ก๋ง ์ด๋ฃจ์ด์ง ‘()’์ ‘[]’๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด์ด๋ค.
- ๋ง์ผ X๊ฐ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด์ด๋ฉด ‘(X)’์ด๋ ‘[X]’๋ ๋ชจ๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด์ด ๋๋ค.
- X์ Y ๋ชจ๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด์ด๋ผ๋ฉด ์ด๋ค์ ๊ฒฐํฉํ XY๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด์ด ๋๋ค.
์๋ฅผ ๋ค์ด ‘(()[[]])’๋ ‘(())[][]’ ๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด์ด์ง๋ง ‘([)]’ ๋ ‘(()()[]’ ์ ๋ชจ๋ ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด์ด ์๋๋ค. ์ฐ๋ฆฌ๋ ์ด๋ค ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด X์ ๋ํ์ฌ ๊ทธ ๊ดํธ์ด์ ๊ฐ(๊ดํธ๊ฐ)์ ์๋์ ๊ฐ์ด ์ ์ํ๊ณ ๊ฐ(X)๋ก ํ์ํ๋ค.
- ‘()’ ์ธ ๊ดํธ์ด์ ๊ฐ์ 2์ด๋ค.
- ‘[]’ ์ธ ๊ดํธ์ด์ ๊ฐ์ 3์ด๋ค.
- ‘(X)’ ์ ๊ดํธ๊ฐ์ 2×๊ฐ(X) ์ผ๋ก ๊ณ์ฐ๋๋ค.
- ‘[X]’ ์ ๊ดํธ๊ฐ์ 3×๊ฐ(X) ์ผ๋ก ๊ณ์ฐ๋๋ค.
- ์ฌ๋ฐ๋ฅธ ๊ดํธ์ด X์ Y๊ฐ ๊ฒฐํฉ๋ XY์ ๊ดํธ๊ฐ์ ๊ฐ(XY)= ๊ฐ(X)+๊ฐ(Y) ๋ก ๊ณ์ฐ๋๋ค.
์๋ฅผ ๋ค์ด ‘(()[[]])([])’ ์ ๊ดํธ๊ฐ์ ๊ตฌํด๋ณด์. ‘()[[]]’ ์ ๊ดํธ๊ฐ์ด 2 + 3×3=11 ์ด๋ฏ๋ก ‘(()[[]])’์ ๊ดํธ๊ฐ์ 2×11=22 ์ด๋ค. ๊ทธ๋ฆฌ๊ณ ‘([])’์ ๊ฐ์ 2×3=6 ์ด๋ฏ๋ก ์ ์ฒด ๊ดํธ์ด์ ๊ฐ์ 22 + 6 = 28 ์ด๋ค.
์ฌ๋ฌ๋ถ์ด ํ์ด์ผ ํ ๋ฌธ์ ๋ ์ฃผ์ด์ง ๊ดํธ์ด์ ์ฝ๊ณ ๊ทธ ๊ดํธ๊ฐ์ ์์์ ์ ์ํ๋๋ก ๊ณ์ฐํ์ฌ ์ถ๋ ฅํ๋ ๊ฒ์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๊ดํธ์ด์ ๋ํ๋ด๋ ๋ฌธ์์ด(์คํธ๋ง)์ด ์ฃผ์ด์ง๋ค. ๋จ ๊ทธ ๊ธธ์ด๋ 1 ์ด์, 30 ์ดํ์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๊ทธ ๊ดํธ์ด์ ๊ฐ์ ๋ํ๋ด๋ ์ ์๋ฅผ ์ถ๋ ฅํ๋ค. ๋ง์ผ ์ ๋ ฅ์ด ์ฌ๋ฐ๋ฅด์ง ๋ชปํ ๊ดํธ์ด์ด๋ฉด ๋ฐ๋์ 0์ ์ถ๋ ฅํด์ผ ํ๋ค.
ํ์ด
๋ถ๋ฐฐ๋ฒ์น์ ์ด์ฉํ๋ ๋ฌธ์ !
์ฐ์ ์ฌ๋ ๊ดํธ๊ฐ ๋์ค๋ฉด ๊ดํธ์ ๊ฐ์ ๊ณฑํด์ฃผ๊ณ , ๋ซ๋ ๊ดํธ๋ ์ด์ ๋ฌธ์๊ฐ ์ฌ๋ ๊ดํธ์ผ ๊ฒฝ์ฐ์๋ง ์ง๊ธ๊น์ง ๊ณฑํ ๊ฐ์ ๋ํด์ค๋ค. ๋ซ๋ ๊ดํธ๊ฐ ๋์ค๋ฉด ํ ๊ดํธ์ ๋ํ ์ฐ์ฐ์ด ๋๋ฌ์ผ๋ฏ๋ก ๋ค์ ๊ดํธ๊ฐ์ ๋๋ ์ค ํ ์ฐ์ฐ์ ์งํํ๋ค.
#include <iostream>
#include <stack>
#include <map>
using namespace std;
/* [๋ถ๋ฐฐ๋ฒ์น ์ด์ฉ]
* (()[[]]) = 2*(2+3*(3)) = 2*2 + 2*3*3
* ( : 2๋ฐฐ
* (( : 4๋ฐฐ
* (([ : 4 ๋ํด์ฃผ๊ณ ๋ค์ ๊ฒ์ 2๋ฐฐ(2๋ก ๋๋๊ธฐ)
* (()[ : 6๋ฐฐ
* (()[[ : 18๋ฐฐ
* (()[[] : 18 ๋ํด์ฃผ๊ณ ๋ค์ ๊ฒ์ 6๋ฐฐ(3์ผ๋ก ๋๋๊ธฐ)
* (()[[]] : ๊ฐ์ด ๋์จ ๊ฒ์ด ์๋! []์ฒ๋ผ ๋ฐ๋ก ์ ๋ฌธ์๊ฐ ์ฌ๋ ๊ดํธ์ผ ๋๋ง ๊ฐ์ด ๋์จ๋ค
* ๋ค์ ๊ฒ๋ค์ 2๋ฐฐ(3์ผ๋ก ๋๋๊ธฐ)
* (()[[]]) : ๊ฐ์ด ๋์จ ๊ฒ์ด ์๋! ๋ค์ ๊ฒ๋ค์ 1๋ฐฐ(2๋ก ๋๋๊ธฐ)
*/
int calc(string s) {
stack<char> st;
map<char, int> num;
map<char, char> bracket;
// ๊ดํธ ์๊ณผ ๊ฐ ์ ์ฅ
num['('] = 2;
num['['] = 3;
bracket[')'] = '(';
bracket[']'] = '[';
int answer = 0;
int tmp = 1;
for (int i = 0; i < s.length(); i++) {
char c = s[i];
switch (c) {
case '(':
case '[': // ์ฌ๋ ๊ดํธ : ์ผ๋จ ๊ณฑ์
st.push(c);
tmp *= num[c];
break;
case ')':
case ']': // ๋ซ๋ ๊ดํธ : tmp ๊ฐ ๋๋๊ธฐ
if (st.empty() || st.top() != bracket[c]) {
return 0;
}
if (s[i - 1] == bracket[c]) // ๋ฐ๋ก ์ ๋ฌธ์๊ฐ ์ฌ๋ ๊ดํธ์ธ ๊ฒฝ์ฐ : ๋ํด์ค๋ค
answer += tmp;
tmp /= num[bracket[c]];
st.pop();
break;
}
}
if (st.empty()) // ์ฌ๋ฐ๋ฅธ ๊ดํธ์ธ ๊ฒฝ์ฐ
return answer;
return 0;
}
int main() {
string s;
cin >> s;
cout << calc(s);
}
'โจ Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค/C++] 11866๋ฒ: ์์ธํธ์ค ๋ฌธ์ 0 (0) | 2022.07.31 |
---|---|
[๋ฐฑ์ค/C++] 18115๋ฒ: ์นด๋ ๋๊ธฐ (0) | 2022.07.24 |
[๋ฐฑ์ค/C++] 2108๋ฒ: ํต๊ณํ (0) | 2022.07.24 |
[๋ฐฑ์ค/C++] 1213๋ฒ: ํฐ๋ฆฐ๋๋กฌ ๋ง๋ค๊ธฐ (0) | 2022.07.24 |
[๋ฐฑ์ค/C++] 20920๋ฒ: ์๋จ์ด ์๊ธฐ๋ ๊ดด๋ก์ (0) | 2022.07.17 |
๋๊ธ