[백준] 2504 괄호의 값 (자료구조) - Java

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

2504번: 괄호의 값

 

 

문제 상황

4개의 기호 (, ), [, ]를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ()와 []는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 (X)이나 [X]도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 (()[[]])나 (())[][]는 올바른 괄호열이지만 ([)]나 (()()[] 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. () 인 괄호열의 값은 2이다.
2. [] 인 괄호열의 값은 3이다.
3. (X) 의 괄호값은 2×값(X) 으로 계산된다.
4. [X] 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 (()[[]])([]) 의 괄호값을 구해보자. ()[[]] 의 괄호값이 2 + 3×3=11 이므로 (()[[]])의 괄호값은 2×11=22 이다. 그리고 ([])의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

 

 

접근법

가장 최근에 열린 괄호가 가장 먼저 닫혀야한다

→ 나중에 추가된 괄호가 먼저 닫힘

→ 후입선출의 스택을 활용

분배법칙

(()[[]])([])

2(2+(33)) ⇒ 22 + 2(3*3)

mul : 곱을 저장하는 변수 , 초기값 1

ans : 합을 저장하는 변수, 초기값 0

• 괄호가 열림 (
  • 스택에 괄호 push
  • mul = mul * 2 or mul = mul * 3
• 괄호가 닫힘 )
  • 스택 최근 값이 ( 이 아니거나, 스택이 비어있는 경우 → 잘못된 문자열
  • 올바른 문자열일 경우, 문자열의 바로 이전 값이 ( 인 경우 mul 을 ans에 저장
  • 스택 pop, mul/2

 

 

문제 풀이

switch-case문 사용 - 알고리즘은 맞지만 백준 정답인정X

import java.io.BufferedReader;
import java.io.IOException;
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 str = br.readLine();
        System.out.println(new Solution().solution(str));

        br.close();
    }
}

class Solution {
    public int solution(String str) {
        int mul = 1;
        int answer = 0;

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            switch (str.charAt(i)) {
                case '(':
                    stack.push('(');
                    mul *= 2;
                    break;

                case '[':
                    stack.push('[');
                    mul *= 3;
                    break;

                case ')':
                    if (stack.isEmpty() || stack.peek() != '(') { //올바른 문자열이 아닌 경우
                        answer = 0;
                        break;
                    }
                    if (str.charAt(i - 1) == '(') {
                        answer += mul; 
                    }
                    stack.pop();
                    mul /= 2;       // 닫힌 괄호에 대한(이미 계산된) 값 제외
                    break;

                case ']':
                    if (stack.isEmpty() || stack.peek() != '[') { //올바른 문자열이 아닌 경우
                        answer = 0;
                        break;
                    }
                    if (str.charAt(i - 1) == '[') {
                        answer += mul;
                    }
                    stack.pop();
                    mul /= 3;
                    break;
            }
        }

        if (!stack.isEmpty()) {
            return 0;
        } else {
            return answer;
        }

    }
}

if문 사용 - 백준 정답O

import java.io.BufferedReader;
import java.io.IOException;
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 str = br.readLine();
        System.out.println(new Solution().solution(str));

        br.close();
    }
}

class Solution {
    public int solution(String str) {
        int mul = 1;
        int answer = 0;

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == '('){
                stack.push('(');
                mul *= 2;
            } else if( str.charAt(i) == '['){
                stack.push('[');
                mul *= 3;
            } else if( str.charAt(i) == ')'){
                if (stack.isEmpty() || stack.peek() != '(') { //올바른 문자열이 아닌 경우
                    answer = 0;
                    break;
                }
                if (str.charAt(i - 1) == '(') {
                    answer += mul;
                }
                stack.pop();
                mul /= 2;       // 닫힌 괄호에 대한(이미 계산된) 값 제외
            } else if( str.charAt(i) == ']'){
                if (stack.isEmpty() || stack.peek() != '[') { //올바른 문자열이 아닌 경우
                    answer = 0;
                    break;
                }
                if (str.charAt(i - 1) == '[') {
                    answer += mul;
                }
                stack.pop();
                mul /= 3;
            }
        }

        if (!stack.isEmpty()) {
            return 0;
        } else {
            return answer;
        }

    }
}