[백준 JAVA] 2504 괄호의 값

2504 괄호의 값

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

문제설명

Stack을 사용한 괄호열 값 계산

접근방식

O(n) 선형 시간복잡도

 

문자열을 한 번 순회하며 입력받은 문자 만큼 스택에 넣고 빼는 연산을 수행한다.

문제 조건 분석 과정

• 1. 입력받은 괄호열을 Stack<Character>을 사용하여 짝을 맞춘다.2. 문자열을 순회하면서
• 각 문자((, ), [, ])에 값을 대입한다.
  • (가 들어오면 스택에 저장하고, tmp에 2를 곱한다
  • [가 들어오면 스택에 저장하고, tmp에 3을 곱한다.
  • )가 들어오면 스택이 비어있거나 스택의 맨 위가 (가 아니면 false로 처리한다.
  • 이전에 (가 있었다면 그에 해당하는 값(tmp)을 answer에 더하고, tmp를 나눈다.
    • ]가 들어오면 스택이 비어있거나 스택의 맨 위가 (가 아니면 false로 처리한다.
    • 이전에 [가 있었다면 그에 해당하는 값(tmp)을 answer에 더하고, tmp를 나눈다.
  문자열을 모두 처리한 후에도 스택에 남아 있는 괄호가 있다면 올바르지 않은 괄호열로 처리한다.
• 곱셈 결과를 담은 answer을 출력한다.

사용된 자료구조

• Stack: 스택을 사용하여 괄호의 짝을 맞추고, 각 괄호열의 값을 계산한다.

전체코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine().trim(); // 괄호열 입력 받기

        Stack<Character> stack = new Stack<>(); // 괄호를 저장할 스택
        int answer = 0; // 괄호열의 값 저장할 변수
        int tmp = 1; // 현재 괄호열의 값을 저장할 변수

        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);

            if (ch == '(') {
                stack.push(ch); // '(' 괄호 스택에 저장
                tmp *= 2; // '(' 괄호의 값은 2
            } else if (ch == '[') {
                stack.push(ch); // '[' 괄호 스택에 저장
                tmp *= 3; // '[' 괄호의 값은 3
            } else if (ch == ')') {
                if (stack.isEmpty() || stack.peek() != '(') { // 올바르지 않은 괄호열인 경우
                    answer = 0;
                    break;
                }
                if (i > 0 && input.charAt(i - 1) == '(') { // '()' 괄호열의 값 처리
                    answer += tmp;
                }
                stack.pop(); // '(' 괄호 처리
                tmp /= 2;
            } else if (ch == ']') {
                if (stack.isEmpty() || stack.peek() != '[') { // 올바르지 않은 괄호열인 경우
                    answer = 0;
                    break;
                }
                if (i > 0 && input.charAt(i - 1) == '[') { // '[]' 괄호열의 값 처리
                    answer += tmp;
                }
                stack.pop(); // '[' 괄호 처리
                tmp /= 3;
            }
        }

        if (!stack.isEmpty()) { // 스택에 남아있는 괄호가 있는 경우
            answer = 0;
        }

        System.out.println(answer); // 결과 출력

        br.close();
    }
}