백준 2504 풀이

괄호의 값

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


풀이

스택에 입력받은 괄호들을 순서대로 넣다가 닿는 괄호가 들어오면 스택에서 해당하는 여는 괄호가 나올때까지 팝하면서 괄호가 정상적이지 않다면 루프를 빠져나오고 정상적이면 문제의 조건에 맞게 수식을 계산하여 다시 스택에 넣어주는 방식으로 구현했다.

입력으로 다양한 값이 들어올 수 있어 반례를 찾는데 어려웠지만 반례를 찾을 수 있었고 문제를 해결했다.

나같은 경우 반례가 (()]였다.

닫는 괄호의 맞는 짝이 아니어도 값을 스택에 넣어 계산을 하는 문제가 있어 이 부분을 수정했더니 통과되었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;

public class Main {
    static int Answer;
    static int n, m;
    static int[] p, rank, arr;
    static ArrayList<String> ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<String> stack = new Stack<>();
        String[] line = br.readLine().split("");
        loop:
        for (String s : line) {
            stack.push(s);
            if (stack.peek().equals(")")) {
                stack.pop();
                if (stack.isEmpty() || stack.peek().equals(")") || stack.peek().equals("[")) {
                    break;
                } else {
                    int sum = 0;
                    while (!stack.peek().equals("[") && !stack.peek().equals("(")) {
                        String val = stack.pop();
                        sum = sum + Integer.parseInt(val);
                        if(stack.isEmpty()) {
                            break loop;
                        }
                        if(stack.peek().equals("["))
                            break loop;
                    }
                    String t = stack.pop();
                    if (sum == 0)
                        sum = 1;
                    sum = sum * 2;
                    stack.push(Integer.toString(sum));
                }
            } else if (stack.peek().equals("]")) {
                stack.pop();
                if (stack.isEmpty() || stack.peek().equals("]") || stack.peek().equals("(")) {
                    break;
                } else {
                    int sum = 0;
                    while (!stack.peek().equals("[") && !stack.peek().equals("(")) {
                        String val = stack.pop();
                        sum = sum + Integer.parseInt(val);
                        if(stack.isEmpty()) {
                            break loop;
                        }
                        if(stack.peek().equals("("))
                            break loop;
                    }
                    String t = stack.pop();
                    if (sum == 0)
                        sum = 1;
                    sum = sum * 3;
                    stack.push(Integer.toString(sum));
                }
            }
        }
        if (stack.contains("(") || stack.contains("[") || stack.contains("]") || stack.contains(")")
                || stack.isEmpty()) {
            bw.write("0\n");
        } else {
            int ans = stack.stream().mapToInt(Integer::parseInt).sum();
            bw.write(ans + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

좋은 웹페이지 즐겨찾기