[백준] 2504 괄호의 값 - Java / Python

 

 

 

자료구조에서 자주 출제되는 괄호 문제이다.

스택을 사용해 해결할 수 있다.

 

다른 문제와는 다르게 괄호마다 값이 주어지고 이 값들을 계산해야 한다.

 

1. 여는 괄호가 나오면 스택에 넣어준다.

2. 닫는 괄호가 나오면 pop을 진행한다.

 

위 부분은 여러 문제에서 다룬 내용과 같지만, 값을 계산하는 부분에서 따로 처리가 필요하다.

 

() 세트가 2 [] 세트가 3이라고 했으니, 여는 괄호가 나올 때 만들어 둔 연산자 변수에 괄호에 따라 2와 3을 곱해주고,

닫는 괄호가 나올 때 만들어 둔 연산자 변수에 괄호에 따라 2와 3을 나눠줘야 한다.

 

정답 변수를 갱신하는 경우는 한 칸 전의 괄호가 세트를 이룰 경우이다.

 

예를 들어, ( ( ( ) ) ) 같은 입력이 주어졌을 때, 4번째 반복을 시행할 때 정답 변수를 갱신한다.

 

Java

 

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		String str = br.readLine();

		Stack<Character> st = new Stack<>();
		int ans = 0;
		int temp = 1;

		for(int i=0; i<str.length(); i++){

			if(str.charAt(i)=='('){
				st.push('(');
				temp = temp * 2;
			}else if(str.charAt(i)=='['){
				st.push('[');
				temp = temp * 3;
			}else if(str.charAt(i)==')'){
				if(st.empty()||st.peek()!='('){
					ans = 0;
					break;
				}else if(str.charAt(i-1)=='('){
					ans = ans + temp;
				}		
					st.pop();
					temp = temp / 2;
			}else if(str.charAt(i)==']'){
				if(st.empty()||st.peek()!='['){
					ans =0;
					break;
				}else if(str.charAt(i-1)=='['){
					ans = ans + temp;
				}
					st.pop();
					temp = temp / 3;
			}
		}

		if(st.empty()){
			System.out.println(ans);
		}else{
			System.out.println(0);
		}


	}
}

 

 

Python

 

파이썬은 스택 자료구조를 따로 제공하지 않기 때문에 리스트를 사용해서 스택을 구현해 풀었다.

 

str = list(input())

st = []
ans =0
temp =1

for i in range(len(str)):

    if str[i] == '(':
        st.append('(')
        temp = temp * 2

    elif str[i] == '[':
        st.append('[')
        temp = temp * 3

    elif str[i] == ')':
        if not st or st[-1] != '(':
            ans = 0
            break
        elif str[i-1] == '(':
            ans = ans + temp
        st.pop()
        temp = temp / 2

    elif str[i] ==']':
        if not st or st[-1] != '[':
            ans = 0
            break
        elif str[i-1] == '[':
            ans = ans + temp
        del st[-1]
        temp = temp / 3

if(st):
    print(0)
else:
    print(int(ans))