[Baekjoon(JAVA) - Algorithm] 2504번: 괄호의 값

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

 

---

이 문제는 스택으로 푸는데 java.util에서 제공하는 Stack을 사용할 것이다.

참고로 java.util에서 제공하는 Stack은 thread-safe하다.
이유는 Stack의 내부 구조를 보면 모든 메서드에 `synchronized`가 붙어 있기 때문이다.

 

Answer

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

public class Main {
    public static void main(String[] args) {
        String brackets = "";

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            brackets = br.readLine();
        } catch (IOException e) {
            System.err.println("ERROR = " + e.getMessage());
        }

        Stack<Character> bracketStack = new Stack<>();
        int tempNum = 1;
        int answer = 0;
        char prevBracket = ' ';

        loop:
        for (char bracket : brackets.toCharArray()) {
            switch (bracket) {
                case '(' :
                    tempNum *= 2;
                    bracketStack.push(bracket);
                    break;
                case '[':
                    tempNum *= 3;
                    bracketStack.push(bracket);
                    break;
                case ')':
                    if (bracketStack.isEmpty() || !bracketStack.peek().equals('(')) {
                        answer = 0;
                        break loop;
                    } else if (prevBracket == '(') {
                        answer += tempNum;
                    }
                    tempNum /= 2;
                    bracketStack.pop();
                    break;
                case ']':
                    if (bracketStack.isEmpty() || !bracketStack.peek().equals('[')) {
                        answer = 0;
                        break loop;
                    } else if(prevBracket == '[') {
                        answer += tempNum;
                    }
                    tempNum /= 3;
                    bracketStack.pop();
                    break;
            }
            prevBracket = bracket;
        }
        
        if (!bracketStack.isEmpty()) {
            answer = 0;
        }
        System.out.println(answer);
    }
}

 

Code Review

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    brackets = br.readLine();
} catch (IOException e) {
    System.err.println("ERROR = " + e.getMessage());
}

`try-with-resources`로 try에 객체의 자원을 받아서 try문이 종료되면 `br.close()`없이 자동으로 자원을 반환한다.

`System.in`으로 사용자로부터 입력받은 데이터를 바이트 스트림으로 받는다.

`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 변환한다.

`BufferedReader` 클래스로 문자 스트림을 읽는다.

 

입력받은 문자열 `br.readLine()`로 읽어서 미리 선언한 `brackets` String 변수에 대입한다.

 

Stack<Character> bracketStack = new Stack<>();
int tempNum = 1;
int answer = 0;
char prevBracket = ' ';

java.util에서 제공하는 Stack으로 객체를 생성한다. (스택의 push(), peek(), pop() 메서드를 사용할 것이다.)

괄호가 갱신될 때마다 계산할 `tempNum`을 1로 선언한다.

올바른 닫는 괄호가 나올 때 정답을 계산할 `answer`을 0으로 선언한다.

닫는 괄호가 나왔을 때 바로 이전의 괄호가 올바른 여는 괄호인지 확인하기 위해 이전 괄호를 담을 `prevBracket` 변수를 선언한다.

 

이제 문제의 핵심 코드를 보자.

loop:
for (char bracket : brackets.toCharArray()) {
    switch (bracket) {
        case '(' :
            tempNum *= 2;
            bracketStack.push(bracket);
            break;
        case '[':
            tempNum *= 3;
            bracketStack.push(bracket);
            break;
        case ')':
            if (bracketStack.isEmpty() || !bracketStack.peek().equals('(')) {
                answer = 0;
                break loop;
            } else if (prevBracket == '(') {
                answer += tempNum;
            }
            tempNum /= 2;
            bracketStack.pop();
            break;
        case ']':
            if (bracketStack.isEmpty() || !bracketStack.peek().equals('[')) {
                answer = 0;
                break loop;
            } else if(prevBracket == '[') {
                answer += tempNum;
            }
            tempNum /= 3;
            bracketStack.pop();
            break;
    }
    prevBracket = bracket;
}

괄호만 비교하면 되므로 switch-case를 사용하는 것이 if문 보다 가독성이 좋아 보여서 사용했다.

 

switch-case의 case문 안에서 for문 자체를 탈출해야 할 때가 있는데 여기서의 break는 switch-case를 탈출한다.

따라서 `labeled-loop`를 사용했다.

for문 앞에 이름을 정해줌으로써 for문 어디서든 이 이름으로 탈출할 수 있게 된다.

 

반복문은 향상된 for문을 사용하여 입력받은 괄호 문자열로 괄호 문자 하나씩 반복하도록 한다.

 

우선 문제를 풀기 위한 단계는 아래와 같다.

1. 여는 괄호가 스택에 쌓일 때마다 괄호에 맞는 값(2 또는 3)을 곱한다.
2. 닫는 괄호가 나오면 이전 괄호와 짝이 맞는 경우에만 정답에 더하고,
   닫는 괄호에 맞는 값(2 또는 3)을 나눈 후 스택을 하나 뺀다.
3. 위를 반복하여 정답을 구한다.

 

이제 문제의 핵심 코드를 보자.

향상된 for문으로 입력받은 괄호열에서 괄호 하나씩 뽑아온다.

뽑아온 괄호를 switch-case 조건으로 로직을 실행한다. (각 조건은 여는 괄호와 닫는 괄호로 구분하면 편한다.)

• 여는 괄호 '('
  1. `tempNum`에 2를 곱한다.
  2. 괄호 스택인 `bracketStack`에 현재 괄호 `bracket`를 `push()` 메서드로 스택을 쌓는다.
• 여는 괄호 '['
  1. `tempNum`에 3을 곱한다.
  2. 괄호 스택인 `bracketStack`에 현재 괄호 `bracket`를 `push()` 메서드로 스택을 쌓는다.
• 닫는 괄호 ')'
  1. 괄호 스택인 `bracketStack`이 비어있거나, 가장 상위의 값이 '('가 아니라면 입력받은 괄호열 자체가 잘못된 경우이기 때문에 `answer`에 0을 대입하고 for문의 이름으로 break 해줌으로써 반복문을 즉시 탈출한다.
  2. 1번의 조건 false로 통과 후,
     이전 괄호가 '('일 때 `answer`에 지금까지 곱해진 `tempNum`을 더한다.
  3. 1번의 조건 false로 통과 후,
     `tempNum`에 2를 나누고,
     괄호 스택인 `bracketStack`에서 가장 상위의 값을 `pop()` 메서드로 스택을 제거한다.
• 닫는 괄호 ']'
  1. 괄호 스택인 `bracketStack`이 비어있거나, 가장 상위의 값이 '('가 아니라면 입력받은 괄호열 자체가 잘못된 경우이기 때문에 `answer`에 0을 대입하고 for문의 이름으로 break해줌으로써 반복문을 즉시 탈출한다.
  2. 1번의 조건 false로 통과 후,
     이전 괄호가 '['일 때 `answer`에 지금까지 곱해진 `tempNum`을 더한다.
  3. 1번의 조건 false로 통과 후,
     `tempNum`에 3을 나누고,
     괄호 스택인 `bracketStack`에서 가장 상위의 값을 `pop()` 메서드로 스택을 제거한다.

위를 괄호열의 각 괄호 문자마다 반복하며,

마지막에는 다음에 사용할 이전 괄호 `prevBracket`에 현재 괄호 `bracket`을 대입한다.

 

풀면서 `answer`에 값을 더할 때,

이전 괄호 `prevBracket`가 필요 없어 보여서 `peek()` 메서드로 비교하느라 곤경에 처했었다.

(이전 괄호가 있어야 현재까지 곱해진 `tempNum`을 `answer`에 무작정 더하지 않고 올바르게 나눌 수 있다.)

따라서 예시 '(()[[]])'를  아래 표로 정리해 본다.

bracket	bracketStack	tempNum	prevBracket	answer
		1		0
(	(	1 * 2 = 2	-> (
(	((	2 * 2 = 4	( -> (
)	(( + ) -> (	4 / 2 = 2	( -> )	0 + 4 = 4
[	([	2 * 3 = 6	) -> [
[	([[	6 * 3 = 18	[ -> [
]	([[ + ] -> ([	18 / 3 = 6	[ -> ]	4 + 18 = 22
]	([ + ] -> (	6 / 3 = 2	] -> ]
)	( + )	2 / 2 = 1	] -> )

(이전 괄호로 비교를 안 해서 헷갈린 곳은 파란색 부분이었다.)

 

if (!bracketStack.isEmpty()) {
    answer = 0;
}

위의 로직에서 괄호 스택 `bracketStack`이 다 비워지지 않으면 괄호열이 잘못된 경우이니 `answer`에 0을 대입한다.

 

Result

(스택은 알고 있었지만 매끄럽게 풀지 못해서 다음에 다시 풀어봐야겠다..)