[골드 5] 괄호의 값

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

2504번: 괄호의 값

풀기 전:

괄호 문제다 무조건 스택이고 쉬울 것 같은데?

 

푸는 중:

어려운데?

닫는 괄호가 나왔을 때 어디 숫자까지 묶어서 곱 더하기 해야 하는지 모르겠네 다른 방법 찾자

 

아 그냥 숫자 넣으면 풀리겠는데?

 

풀었음:

 

스택에는 (, [, 숫자 3종류가 있을 수 있다

)랑 ] 들어올 때 숫자가 peek()에 있다면 곱해주고 없다면 숫자로 변환 

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

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

        Stack<String> stack = new Stack<>();
        String tmp;
        boolean input_correct = true;

        String input = br.readLine();

        // 유효성 검사
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(' || input.charAt(i) == '[')
                stack.add(String.valueOf(input.charAt(i)));
            else if (stack.isEmpty())
                input_correct = false;
            else if (input.charAt(i) == ')' && !stack.pop().equals("("))
                input_correct = false;
            else if (input.charAt(i) == ']' && !stack.pop().equals("["))
                input_correct = false;
        }

        if (!input_correct || !stack.isEmpty()) {
            sb.append(0);
            System.out.println(sb);
            System.exit(0);
        }

일단 무난하게 입력받고 올바른 식인지 먼저 한번 순회하며 검사한다

1.  () [] 짝이 안 맞는 경우

2. ) ] 가 들어왔는데 스택이 비어있는 경우

3. 마지막에 ( [ 가 들어와서 혼자 있는 경우

        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(' || input.charAt(i) == '[')
                stack.add(String.valueOf(input.charAt(i)));
            else {
                tmp = stack.pop();
                if (input.charAt(i) == ')') {
                    if (tmp.equals("("))
                        stack.push("2");
                    else {
                        stack.pop();
                        stack.push(String.valueOf(Integer.parseInt(tmp) * 2));
                    }

                } else {
                    if (tmp.equals("["))
                        stack.push("3");
                    else {
                        stack.pop();
                        stack.push(String.valueOf(Integer.parseInt(tmp) * 3));
                    }
                }

                tmp = stack.pop();
                if (!stack.isEmpty() && !stack.peek().equals("(") && !stack.peek().equals("["))
                    stack.push(String.valueOf(Integer.parseInt(stack.pop()) + Integer.parseInt(tmp)));
                else
                    stack.push(tmp);

            }
        }

        sb.append(stack.pop());
        System.out.println(sb);

    }
}

다시 또 한 바퀴 돌면서 검사한다

1. ( [ 스택에 넣기

2. ) ] 숫자 없이 있는 경우 숫자로 변환

2. 숫자) 숫자] 인 경우는 곱하기

3. 숫자를 마지막에 넣었는데 그 아래 peek()가 숫자인 경우 더하기

 

O(N)