c++ 2504번 괄호의 값 (백준)

#include <cstdio>
#define M 100

class Stack { //스택 
	int data[M];
	int top;
public:
	Stack() : top(0) {}
	bool isEmpty() {return top==0;}
	void push(int e) {data[top++] = e;} //넣기 
	int pop() {return data[--top];} //빼기 
	int peek() {return data[top-1];} //가장 최신꺼 반환 
};

int main(void) {
	Stack s; //스택만들기 
	char str[31]; //문자열 배열 
	scanf("%s", str); //문자열 받기 
	
	for(int i=0; str[i]!='\0'; i++) { //올바른 괄호인지 파악 
		if(str[i] == ']' || str[i] == ')') {
			if(s.isEmpty() || (str[i] == ']' && s.peek() != '[') || (str[i] == ')' && s.peek() != '('))
			{
				printf("0"); //스택에 아무것도 없을 때, ] ) 가 들어오거나, (], [) 인 경우 
				return 0;
			} else s.pop(); //(), [] 일 경우 스택에서 꺼냅니다. 
		} else s.push(str[i]); //(, [은 스택에 집어넣습니다. 
	}
	
	if(!s.isEmpty()) //스택에 요소가 남아있다면, 짝을 짓지 못하는 것이 존재한다는 의미 
	{
		printf("0");
		return 0;
	}
	
	
	//()은 2으로, []은 3으로 처리합니다. 여는 괄호가 누적 될 수록 가중치에 곱하기를 해줍니다. 
	//닫는 괄호가 나오면,  가중치를 ans에 더한다음, 가중치를 감소시킵니다. 
    //여는 괄호가 나오면, flag = 1, 닫는 괄호가 나오면  flag = 0
    //flag = 1 일 때 닫는 괄호가 나온다면 가중치v를 sum에 더해준 후, flag = 0으로 바꾸어 줍니다.
	int ans = 0;
	int v=1;
	int flag = 0;
	for(int i=0; str[i]!='\0'; i++) { 
		if(str[i]=='(') {
			v*=2;
			flag = 1;
		}
		else if(str[i]=='[') {
			v*=3;
			flag = 1;
		}
		else if(str[i]==')') { 
			if(flag) ans += v;
			v/=2;
			flag = 0;
		}
		else if(str[i]==']') {
			if(flag) ans += v;
			v/=3;
			flag = 0;
		}
	}
	printf("%d", ans);
}

 

풀이 : 스택

 

스택을 이용하여, 주어진 괄호들이 짝을 이룰수 있는지를 판별합니다.

스택에서 괄호들을 하나씩 넣어준 다음 (), [] 이렇게 짝을 만들게 되면 스택에서 삭제합니다.

 

1. 스택이 비어있을 때, ), ] 가 들어오게 되면 반드시 짝을 지을 수가 없게 됩니다.

2. (], [) 이런 경우에는 짝을 지을 수가 없게 됩니다.

3. 모든 괄호를 집어넣었으나, 스택이 비어있지 않은 경우, 이는 짝을 만들지 못했다는 의미입니다.

 

위의 1,2,3 이 아닌 경우가, 괄호의 값을 구할 수 있는 괄호입니다.

위의 1,2,3을 만족하는 경우는 0을 출력한 다음 종료합니다.

 

괄호의 값을 구하는 법

누적합을 담을 변수를 sum

가중치를 v

괄호가 열릴땐 1로, 닫힐땐 0으로 해줄 flag을 만들어 줍니다.

 

( 이면 가중치에 *2

[ 이면 가중치에 *3

 

그러다가 ), ] 을 만난다면 가중치를 sum에 더해준다음

 

) 이면 가중치에 /2

] 이면 가중치에 /3

만큼 해줍니다.

그러면서 flag는 0으로 바꾸어 줍니다.

 

여기서 중요한 점은 flag가 1이고 닫는 괄호를 만났을 때만 sum에 가중치를 누적할 수 있습니다.

 

 

괄호	(	(	)	[	[	]	]	)	(	[	]	)
v=1	2	4	2	6	18	6	2	1	2	6	3	1
sum=0			4			22					28
flag = 0	1	1	0	1	1	0	0	0	1	1	0	0

 

(()[[]])([]) //28

 

flag 을 사용하는 이유는

사용하지 않으면

(()) 4가 아니라 6이 됩니다

(실제로는 2(2))

 

이러한 오류를 방지하기위해, 닫는 괄호가 나올때 값을 더해준다음, 다시 여는 괄호가 나오기 전까지는 다른 닫는 괄호들을 무시해 줍니다. (flag을 이용하여)

 

https://www.acmicpc.net/problem/2504

2504번: 괄호의 값