백준

[백준] 2504번 괄호의 값 (java, 구현, stack)

해랑쓰 2021. 4. 19. 12:48
728x90
반응형

www.acmicpc.net/problem/2504

 

2504번: 괄호의 값

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.  만일

www.acmicpc.net

구현인데 어려웠다 

괄호가 코딩테스트에 자주 나오는 이유 ~ 

 

중첩된 것의 계산을 어떻게 해줄지 떠올리느냐 아니냐가 중요했다 

 

나의 경우 괄호의 깊이를 계산해서 후위계산식으로 만들어서 계산해줄려고 했는데 너무 길고 복잡해서 다른 사람 풀이를 참고 했다.

 

--- 

 

중첩되어서 안쪽에 있는 괄호쌍은 앞에서 곱해온 수에 현재 괄호쌍의 값을 곱한다.

여는 괄호에서 곱해주면 된다. ( 열 때마다 중첩되서 깊어지므로)

 

만약 현재가 닫는 괄호 ) 혹은 ]이고 바로 앞에 (스택말고 받은 문자열!) 여는 괄호 (,[ 가 있다면 앞에 나오는 괄호 쌍과 같은 깊이라서 결과값에 더해준다

 

만약 현재가 닫는 괄호 ) 혹은 ]이고 또 다른 닫는 괄호 ], ) 가 있다면 중첩되는 괄호쌍이므로 

현재 괄호쌍의 값을 또 곱해줘야 한다.

 

--- 참고한 반례

[[[]][]] 36
(()([())]) 28

 

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	static String s;
	static int answer;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		s=sc.next();
		Stack<Integer> st=new Stack<>();
		int temp=1;
		for (int i = 0; i < s.length(); i++) {
			if(s.charAt(i)=='(') {
				st.add(2);
				temp*=2;
			}else if(s.charAt(i)=='[') {
				st.add(3);
				temp*=3;
			}else {//닫는 괄호
				//여는 괄호 없음
				if(st.size()==0) {
					answer=0;
					break;
				}
				
				//다른거 들어옴
				if(s.charAt(i)!=']' && s.charAt(i)!=')') {
					answer=0;
					break;
				}
//				짝 안맞음
				if((s.charAt(i)==']' && st.peek()==2) || (s.charAt(i)==')' && st.peek()==3)) {
					answer=0;
					break;
				}
				
				int cur=2;
				if(s.charAt(i)==']') {
					cur=3;
				}

				//앞에 아무 것도 없거나(가장 바깥 괄호임), 더이상 안에 다른 괄호를 포함하지 않는 경우 계산이 끝나 더해준다.
				if(st.size()==0 || (s.charAt(i-1)=='(' && cur==2) || (s.charAt(i-1)=='[' && cur==3)) {
					answer+=temp;
//					System.out.println(temp);
				}
				
				st.pop();//여는 괄호 pop
				temp/=cur;
				
			}
			
		}
		
		if(st.size()!=0) {
			//모든 괄호가 안닫힘
			answer=0;
		}
		
		System.out.println(answer);
	}
}
728x90
반응형