[백준] 2504. 괄호의 값 (JAVA)

이번에 풀어 볼 문제는 <백준 2504번. 괄호의 값>이다.

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

📌 문제 탐색하기

목표

주어진 괄호열을 읽고 그 괄호 값을 규칙대로 계산하여 출력하기

해야 할 것

1. 계산 규칙 이해하고, 구현하기

2. 입력이 올바르지 못한 괄호열이면 반드시 0 출력하기

입력

[첫줄] 괄호열 (1 ≤ 괄호열의 길이 ≤ 30)

아이디어

1. 계산 규칙 이해하고 구현하기

- '()' 의 값 = 2

- '[]' 의 값 = 3

- '(x)'의 값 = 2*x의 값

- '[x]'의 값 = 3*x의 값

- xy = x의 값+y의 값

 

괄호 문제는 스택을 이용해서 풀 수 있다는 것을 알고 있으니, 이 문제도 스택을 활용해서 해결할 수 있는지 생각해보자.

 

스택에 쌓을 때,  고려해야 할 점은 크게 세 가지이다.

1. 짝이 맞는 지 확인할 수 있어야 한다. 

2. '()' 와 '(x)' 를 구별하려면 인덱스를 스택에 함께 저장해야 한다.

3. '(x)'를 계산하려면, x의 점수를 어딘가에 저장하고 있어야 한다.

 

따라서 스택에 쌓을 때 [ 괄호의 종류, 인덱스, 점수 ] 형태로 저장하기로 했다.

 

먼저, '('나 '[' 가 나오면 일단 스택에 쌓는다.

점수 계산은 괄호가 닫힐 때 해야 한다.

 

점수 계산 방식은 크게 두 가지로 나뉜다.

1) 열고 닫는 괄호가 연달아 나온 경우 

'()' : 2점, '[]' : 3점

 

2) 열고 닫는 괄호가 연달아 나오지 않은 경우

'(x)', '[x]' 와 같은 경우가 이 경우에 해당한다. 이를 연산하기 위해서는  x의 점수를 어딘가에 저장해두어야 한다.

예를 들어, 입력 문자열이 "(()[])"라면 내부의 괄호 값을 먼저 계산해야 한다. ()는 2를, []는 3을 반환한다. 이 값들을 외부의 ()로 전달해야 최종 계산을 할 수 있다. 

 

여기서 아이디어를 얻어 () 과 [] 이 스택에서 빠져나갈 때 가장 밖의 ( 에 자신의 점수를 전달해줘야겠다고 생각했다.

 

즉, 닫히는 괄호가 나오면 스택에서 자신을 제거하기 전에, 바로 아래 있는 괄호에게 자신의 점수를 전달해주고 나간다.

 

그럼 최종 점수는 언제 누적해야할까?

스택이 비게 될 때가 괄호 한 뭉텅이가 끝나는 시점이기 때문에 그때 점수를 누적하도록 하자.

(()[])() 라고 주어졌다면,  (()[]) 까지 진행하면 스택에 남아있는 게 하나도 없게 되므로 그때 최종 점수를 누적하고, 같은 방법으로 () 를 진행한 뒤 최종 점수에 합쳐 주면 된다.

 

2. 입력이 올바르지 못한 괄호열이면 반드시 0 출력하기

중간에 짝이 맞지 않는 괄호가 나오면 0을 바로 출력해주도록 하자.

📌 코드 설계하기

1. input 명령을 받고 스택을 구현한다. 스택에는 [괄호의 종류, 인덱스, 점수] 형태의 배열을 저장할 것이다.

총점을 저장할 totalScore 변수도 선언한다.

 

2. 입력된 괄호 문자열을 하나씩 탐색하며 다음과 같이 조건을 나눠 코드를 구현한다.

 

2-1. '(' 나 '[' 이 나오면 스택에 추가한다. 점수는 0으로 초기화한다.

2-2. ')' 이 나오면, 인덱스 값을 보고 현재점수를 계산한다.

curScore = curIndx - stack.peek()[1] == 1 ? 2 : 2*stack.peek()[2] ;

 

2-3. '[' 이 나오면, 인덱스 값을 보고 현재점수를 계산한다.

curScore = curIndx - stack.peek()[1] == 1 ? 3 : 3*stack.peek()[2] ;

 

2-4. 2-2,2-3을 진행한 뒤 스택에서 가장 윗 원소를 제거한다. 이때, 스택에 남은 원소가 있다면 현재 스택의 가장 윗 원소에게 자신의 점수를 넘겨주고, 만약 스택에 남은 원소가 없다면 totalScore를 업데이트 한다.

stack.pop();
if(!stack.isEmpty()){
     stack.peek()[2] += curScore;
 }else{
   totalScore += curScore;
  }

 

2-5. 중간에 짝이 맞지 않으면 totalScore = 0 으로 설정한 뒤, break 문을 실행하여 탐색을 종료한다.

 

3. 최종적으로 저장된 totalScore를 출력한다.

📌 정답 코드

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

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

        ArrayDeque<int[]> stack = new ArrayDeque<>();
        //[괄호의 종류, 인덱스, 점수]
        //'(' = 0 , '[' = 1

        char[] input = br.readLine().toCharArray();
        int curIndx = 0;
        int totalScore = 0;

        for(char c : input){

            int curScore = 0;
            if(c == '('){
                stack.push(new int[]{0,curIndx, curScore});
            }else if(c =='['){
                stack.push(new int[]{1,curIndx,curScore});
            }else if(c ==')'){

                if(!stack.isEmpty() && stack.peek()[0] == 0){
                    curScore = curIndx - stack.peek()[1] == 1 ? 2 : 2*stack.peek()[2] ;
                    stack.pop();
                    if(!stack.isEmpty()){
                        stack.peek()[2] += curScore;
                    }else{
                        totalScore += curScore;
                    }
                }else{
                    totalScore = 0;
                    break;
                }
            }else if(c ==']'){

                if(!stack.isEmpty()&& stack.peek()[0] == 1){
                    curScore = curIndx - stack.peek()[1] == 1 ? 3 : 3*stack.peek()[2] ;
                    stack.pop();
                    if(!stack.isEmpty()){
                        stack.peek()[2] += curScore;
                    }else{
                        totalScore += curScore;
                    }
                }else{
                    totalScore = 0;
                    break;
                }
            }

            curIndx++;
        }

        System.out.println(totalScore);
    }
}

 

📌 알게 된 것

아이디어를 생각해내기가 정말 오래걸린다..

비슷한 유형을 자꾸 풀어보는 것 밖에 답이 없는 듯 ㅜ