백준 2504 ←클릭
스택을 활용한 문제이다.
변수 설정
op_s: 연산자를 저장하는 스택이다.
num_s: 숫자를 저장하는 스택이다.
cur_s: 현재 사용하는 스택의 번호를 저장하는 변수이다. 처음에 -1로 초기화 되어있다.
v: 괄호를 저장하는 스택인데 input으로 받은 문자열이 유효한 지 판별할 때 사용한다.
아이디어
- 유효성 판단
- 스택에 입력 문자를 삽입
- 여는 괄호일 경우: 스택에 삽입
- 닫는 괄호일 경우:
2-1. 스택의 top이 쌍에 맞는 괄호인 경우 pop
2-2. 스택의 top이 쌍에 맞지 않는 괄호인 경우 break후 0 출력
- 스택에 입력 문자를 삽입
- 값 계산
- 여는 괄호가 나오는 경우 :
- 이전
input값이 여는 괄호((,[)인 경우 현재의 연산자 스택op_s[cur_s]에+를 삽입. - 이전
input값이 닫는 괄호(),])인 경우 현재의 연산자 스택op_s[cur_s]에*를 삽입. - 스택의 번호
cur_s를 1 증가. - 새로운 숫자 스택
num_s[cur_s]에 괄호에 해당하는 값을 삽입한다.
- 닫는 괄호가 나오는 경우:
- 현재 스택의 번호에 해당되는 숫자 스택과 연산자 스택에서 하나씩 꺼내며 연산을 한다.
- 연산의 결과를 상위 스택의 숫자 스택에 삽입한다.
예시
문제에 나온 예시로 설명을 하겠다.
input: ( ( ) [ [ ] ] ) ( [ ] )
일단 문제에서 input의 길이는 최대 30이라고 했으므로 스택은 최대 15개가 사용될 것이므로 stack을 15개 선언해준다.
1. (: 여는 괄호가 입력으로 들어왔으므로 cur_s를 1 증가한다.
cur_s: 0
맨 처음 입력의 경우 앞에 아무 문자도 없기 때문에 연산자를 삽입하지 않는다. 숫자 스택 num_s[0]에 2를 삽입한다.
2. (: 여는 괄호가 입력으로 들어왔다. 이전 입력이 (이기 때문에 현재 연산자 스택 op_s[0]에 *를 삽입하고 cur_s를 1 증가한다. 다음 숫자 스택num_s[1]에 2를 삽입한다.
cur_s: 1
3. ): 닫는 괄호를 만났기 때문에 현재 스택에 있는 연산을 해줘야 한다. 연산의 결과 값은 2이기 때문에 해당 값을 상위 숫자 스택num_s[0]에 삽입하고 cur_s의 값을 1 감소시킨다. 연산을 하는 과정에서 pop을 사용하여 스택들num_s[1]와 op_s[1]을 모두 비워야 한다.
cur_s: 0
4. [: 여는 괄호이기 때문에 이전 입력을 확인한다. 이전 입력은 )이다. 현재의 연산자 스택op_s[0]에 +를 삽입하고 cur_s의 값을 1 증가한다.
cur_s: 1
숫자 스택num_s[1]에 3을 삽입한다.
<후략>
코드
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
int main() {
stack<char> op_s[15];
stack<int> num_s[15];
int cur_s = -1;
string input;
//freopen("input/2504_input.txt", "r", stdin);
cin >> input;
int ans = 0;
bool valid = true;
stack<char> v;
for (int i = 0; i < input.size(); i++) {
if (input[i] == ']') {
if (v.empty() || v.top()!='[') {
valid = false;
break;
}
else {
v.pop();
}
}
else if (input[i] == ')') {
if (v.empty() || v.top() != '(') {
valid = false;
break;
}
else {
v.pop();
}
}
else {
v.push(input[i]);
}
}
if (valid) {
for (int i = 0; i < input.size(); i++) {
//printf("input: %c, cur_s: %d\n", input[i], cur_s);
if (input[i] == '(') {
if (i > 0 && (input[i - 1] == ')' || input[i - 1] == ']') && cur_s > -1) {
op_s[cur_s].push('+');
//printf("op_s[%d].push('+')\n", cur_s);
}
else if (i > 0 && (input[i - 1] == '(' || input[i - 1] == '[') && cur_s > -1) {
op_s[cur_s].push('*');
//printf("op_s[%d].push('*')\n", cur_s);
}
cur_s++;
num_s[cur_s].push(2);
//printf("cur_s: %d, push 2\n", cur_s);
}
if (input[i] == '[') {
if (i > 0 && (input[i - 1] == ')' || input[i - 1] == ']') && cur_s > -1) {
op_s[cur_s].push('+');
//printf("op_s[%d].push('+')\n", cur_s);
}
else if (i > 0 && (input[i - 1] == '(' || input[i - 1] == '[') && cur_s > -1) {
op_s[cur_s].push('*');
//printf("op_s[%d].push('*')\n", cur_s);
}
cur_s++;
num_s[cur_s].push(3);
//printf("cur_s: %d, push 3\n", cur_s);
}
if (input[i] == ')' || input[i] == ']') {//cur_stack¿¡ ´ëÇØ ¿¬»ê
int rst = num_s[cur_s].top();
num_s[cur_s].pop();
while (!op_s[cur_s].empty()) {
if (op_s[cur_s].top() == '+') {
rst += num_s[cur_s].top();
num_s[cur_s].pop();
op_s[cur_s].pop();
}
else {
rst *= num_s[cur_s].top();
num_s[cur_s].pop();
op_s[cur_s].pop();
}
}
cur_s--;
if (cur_s >= 0) {
num_s[cur_s].push(rst);
//printf("num_s[%d].push(%d)\n", cur_s, rst);
}
else {
ans += rst;
//printf("ans: %d\n", ans);
}
}
}
}
cout << ans << endl;
}아이디어2
- 여는 괄호들은 스택에 push
- 닫는 괄호를 만나면 stack에서 숫자들을 pop 해가며 덧셈 연산을 하고, 자기 쌍에 맞는 여는 괄호를 만나면 해당하는 수를 곱함.
- 연산 결과를 다시 스택에 삽입
예시2
후기
stack을 이용하며 풀었는데 사실 DFS에 가까운 풀이 같다. 문제를 처음에 읽었을 때 특정 문자에 대해 스택에 삽입, 연산과정을 분리해서 풀면 쉽게 풀릴 것 같았는데 생각이 안나서 비 효율적인 방법으로 억지로 풀었다. 위 해답은 시간 복잡도는 괜찮지만 공간 복잡도가 높아서 문자열 길이에 제한이 없는 케이스에서는 메모리가 많이 필요할 것이다.
야속하게 이 블로그를 작성하면서 아주 간단한 풀이가 생각나서 아이디어와 예시를 첨부했다 ㅠㅠ. 이 문제가 실버 난이도인 이유가 이렇게 풀면 쉽게 풀리기 때문인 것 같다.
정답~.~
