[BOJ/JAVA] 백준 2504번 괄호의 값 ( 스택 Stack )

 

✔ 문제

난이도 : 골드5 🥇

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

2504번: 괄호의 값

 

주어진 괄호열에 대해서 올바른 괄호일 때  주어진 조건에 맞게 계산하는 문제입니다.

 

 

✔ 문제 풀이

알고리즘 문제를 조금 풀어보았다면 괄호를 보자마자 stack을 떠올릴 수 있을 것입니다.

하나의 괄호는 열고 닫는 괄호로 이루어져 있습니다, 이러한 점을 stack의 LIFO의 특징을 활용하여 괄호에 하나씩 접근할 수 있게 됩니다.

 

( ( ) [ [ ] ] )

 

하지만 3번, 4번, 5번 조건 즉, 위의 예시처럼 괄호 안에 괄호가 있다면 안에 있는 괄호를 먼저 연산하고 감싸져 있는 괄호에 대해서는 곱하기 연산을 수행해야 합니다.

이때, 감싸져 있는 괄호를 구분하면서 올바르게 계산하는 방법이 잘 떠 오리지 않았습니다.😭

 

그래서 풀이 방법을 찾아보았고, 분배법칙을 사용하여 문제를 풀어나가고 있었습니다.

 

 

위의 그림을 보시면 이해가 조금 더 편할 것 같습니다.

 

 

 

간단히 설명하자면 '(' 또는 '[' 같이 여는 괄호를 만났을 경우 괄호를 stack에 넣고 괄호에 해당하는 값을 value 변수에 곱해줍니다.

if( line.charAt(i) == '('){
    stack.push(line.charAt(i));
    value *= 2;
    continue;
}
if( line.charAt(i) == '['){
    stack.push(line.charAt(i));
    value *= 3;
    continue;
}

 

 

')' 또는 ']'를 만났을 경우 괄호 가 끝난 것이므로 누적된 값을 결과 값(result)에 더해줍니다.

💡 이때 이전 괄호가 여는 괄호일 경우에만 result에 값을 더해줍니다.

 

또한 닫힌 괄호를 만났을 때 나누기 연산(value/2,3)을 해주는 이유는 이전의 분배되는 값으로 돌아가기 위함입니다.

if( line.charAt(i) == ')'){
    if( stack.isEmpty() || stack.peek() != '('){
        result = 0;
        break;
    }
    if( line.charAt(i-1) == '('){ // 이전 괄호가 여는 괄호일 경우에만 result에 값을 더해줍니다.
        result += value;
    }

    value /= 2;
    stack.pop();
    continue;
}

if( line.charAt(i) == ']'){
    if( stack.isEmpty() || stack.peek() != '['){
        result = 0;
        break;
    }
    if( line.charAt(i-1) == '['){
        result += value;
    }

    value /= 3;
    stack.pop();
}

 

 

🔎 전체 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main{
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        
        String line = br.readLine();
        Stack<Character> stack = new Stack<>();
        
        int value = 1;
        int result = 0;
        for( int i = 0; i<line.length(); i++){
            
            if( line.charAt(i) == '('){
                stack.push(line.charAt(i));
                value *= 2;
                continue;
            }
            if( line.charAt(i) == '['){
                stack.push(line.charAt(i));
                value *= 3;
                continue;
            }
            
            if( line.charAt(i) == ')'){
                if( stack.isEmpty() || stack.peek() != '('){
                    result = 0;
                    break;
                }
                if( line.charAt(i-1) == '('){
                    result += value;
                }
                
                value /= 2;
                stack.pop();
                continue;
            }
            
            if( line.charAt(i) == ']'){
                if( stack.isEmpty() || stack.peek() != '['){
                    result = 0;
                    break;
                }
                if( line.charAt(i-1) == '['){
                    result += value;
                }
                
                value /= 3;
                stack.pop();
            }
        }
        
        if( !stack.isEmpty()){
            System.out.print(0);
        } else {
            System.out.print(result);
        }

	}
}