[백준][JAVA] 2504 - 괄호의 값

스택 자료구조를 다루는 감이 떨어져 스택 문제를 복습했습니다. 풀고 나니 예상보다 티어가 높은 문제였네요.

 

* 선수지식 : Stack, (List)

 

---

 문제 링크 

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

 

 개요 

"괄호의 짝이 맞는지 확인하고, 괄호의 쌍이 나타내는 값의 합계를 구하세요".

- 괄호 '()'는 감싸고 있는 값들을 전부 합해서 2를 곱해줍니다. 괄호 안이 비었다면 2를 나타냅니다.

- 괄호 '[]'는 감싸고 있는 값들을 전부 합해서 3을 곱해줍니다. 괄호 안이 비었다면 3을 나타냅니다.

() = 2
[] = 3
([]) = 2 * 3 = 6
()[] = 2 + 3
[()[]] = 3 * (2 + 3) = 15
[([])[]] = 3 * ( (2 * 3) + 3 ) = 27

 

이 규칙에 의하여 주어진 문자열을 올바르게 계산해야 하는 문제입니다.

 

 

 코드 

[✅ 정답 코드 - Stack과 List 사용]

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

public class Main_2504 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int N = input.length();

        Stack<Character> st = new Stack<>();
        List<Integer> sums = new ArrayList<>();
        int idx = -1;
        int answer = 0;

        for (int i = 0; i < N; i++) {
           char curr = input.charAt(i);

           if(curr == '(' || curr == '['){
               st.push(curr);
               sums.add(0);
               idx++;
           }else{
               if(st.isEmpty() || !isPair(st.peek(), curr)){
                   System.out.println(0);
                   return;
               }else{
                   st.pop();
                   int total = sums.remove(idx);
                   int result = (total == 0 ? 1 : total) * getMult(curr);
                   if(--idx >= 0){
                       sums.set(idx, sums.get(idx) + result);
                   }else{
                       answer += result;
                   }
               }
           }

        }

        System.out.println(st.isEmpty() ? answer : 0);
    }

    static int getMult(char close){
        return close == ']' ? 3 : 2;
    }

    static boolean isPair(char open, char close){
        if( (open == '(' && close == ')') || (open == '[' && close == ']') )
            return true;
        else
            return false;
    }
}

 

 

 

 해설 

📌Stack과 List

가장 나중에 입력된 괄호들을 가장 먼저 처리해서 결과값을 내고,
그 다음에 가장 먼저 입력된 괄호들을 처리하는 방식으로 문제풀이가 이루어집니다.

(LIFO, FILO)

이런 특성에 가장 적합한 자료구조인 Stack을 이용하겠습니다.

 

그리고 겹겹이 중첩되어 있는 각각의 괄호 안에서 구할 합계를 저장할 수 있어야 합니다.

정수를 추가/제거하기 위해 List를 사용하고,

별도로 idx라는 정수 변수를 사용해 현재 몇 번째로 겹쳐진 괄호 안에서 합계를 구하고 있는지 가리키도록 하였습니다.

 

물론 굳이 List를 쓸 필요는 없고 적당한 크기의 배열을 써도 되지만,
풀이 중에는 한 번 쓰고 제거한다는 점을 좀 더 명확히 하고 혼동을 줄이고자 List를 사용했습니다.

 

/* 스택과 리스트를 선언합니다. */
Stack<Character> st = new Stack<>();
List<Integer> sums = new ArrayList<>();

/* 
 * 리스트의 최근 인덱스를 가리킬 idx 변수입니다. 
 * 리스트가 비어 있을 땐 초기값이 -1이었다가, 
 * 원소가 들어오면서 0, 1, 2 ... 등 실제 인덱스를 나타낼 것입니다. 
*/
int idx = -1;

/* 정답을 저장할 answer 변수입니다. */
int answer = 0;

 

 

📌열린 괄호를 만난 경우

 for (int i = 0; i < N; i++) {
   char curr = input.charAt(i);

/* 현재 괄호가 ( 또는 [와 같이 열린 괄호일 경우 */
   if(curr == '(' || curr == '['){
       st.push(curr);
       sums.add(0);
       idx++;
   }else{
       // ...
   }

}

 

- Stack에 현재 괄호를 집어넣습니다.

- List에 0을 집어넣고, 앞으로 현재 괄호 내부의 계산 결과를 여기다 더해주겠습니다.

- idx가 List에서 현재 괄호의 위치를 가리킬 수 있도록 1만큼 증가시킵니다.

 

📌닫힌 괄호를 만난 경우

문제의 조건에 따르면,

앞서 조건문   curr == '(' || curr == '['  를 통과하지 못한 경우는 무조건 닫힌 괄호 ) 또는 ]를 만나게 됩니다.

 

[1. 괄호 문자의 유효성 확인하기]

짝이 맞는 괄호들을 전부 제거했을 때,
괄호 문자가 유효하지 않는 경우는 크게 두 가지가 있겠습니다.

 

a. 열려 있는 괄호가 없는데 닫힌 괄호가 등장했을 때

열린 괄호가 없다는 것은 다시 말해 현재 스택에 아무것도 없다는 의미겠지요. 

 

b. 괄호가 있는데 서로 짝이 맞지 않을 때

스택의 최상단에 있는 열린 괄호, 현재 등장한 닫는 괄호가 서로 짝이 맞지 않는 상황입니다.

 

다음과 같이 구현하였습니다.

/* 스택이 비어 있거나, 사용자 정의 메서드 isPair의 결과가 false일 경우*/
if(st.isEmpty() || !isPair(st.peek(), curr)){

/* 유효하지 않은 괄호 문자열이므로 0을 출력하고 프로그램을 종료합니다. */
   System.out.println(0);
   return;
}else{
   ...
}

 

/* 사용자 정의 메서드 isPair */ 
/* 두 괄호가 짝이 맞는지 확인하고 true, false를 반환합니다.*/
/* 스택의 최상단에 있는 괄호, 현재 탐색 중인 문자를 비교하는 데 사용하였습니다. */
static boolean isPair(char open, char close){
    if( (open == '(' && close == ')') || (open == '[' && close == ']') )
        return true;
    else
        return false;
}

 

[2. 괄호 문자의 합계 구하기]

괄호가 유효한 것으로 판명이 났다면 알맞은 값을 계산해 줍니다.

괄호를 닫기 전까지 합계가 얼마였는지 저장해 뒀다가,
괄호가 닫히는 순간 종류에 맞게 2 또는 3을 곱한 뒤

바깥 괄호에서 구하고 있는 합계에 더해 줄 것입니다.

if(st.isEmpty() || !isPair(st.peek(), curr)){
   ...
}else{
	/* 짝을 맞춘 열린 괄호는 스택에서 제거해 줍니다.*/
   st.pop();
   
   /* 
    * 정수 변수 total에 지금까지 괄호 내부에서 구한 합계를 저장합니다. 
    * List의 remove는 항목을 제거함과 동시에 제거된 항목을 반환합니다. 
   */
   int total = sums.remove(idx);
   
   /* 
    * 정수 변수 result에 괄호의 종류에 따라 결괏값을 계산해 줍니다.
    * 사용자 정의 메서드 getMult로 괄호의 종류에 따라 얼마를 곱할지 구해 줍니다. 
    * 만일 '()', '[]'과 같이 빈 괄호라서 합계가 0인 경우, 1을 곱해서 2 또는 3으로 만들어 줍니다.
    */
   int result = (total == 0 ? 1 : total) * getMult(curr);
   
   if(--idx >= 0){
   	/* idx를 하나 줄여서 바깥 괄호를 가리키고, 구한 값을 바깥 괄호의 합계에 더해 줍니다. */
       sums.set(idx, sums.get(idx) + result);
   }else{
   	/* idx가 -1일 경우 현재 더 이상 열린 괄호가 없으므로, 구하고자 하는 총 합계에 더해 줍니다. */
       answer += result;
   }
}

/* 괄호의 종류에 따라 곱할 값을 반환하는 getMult 메서드*/
static int getMult(char close){
	// 매개변수 close가 ]라면 3을, 아니라면 )로 간주하고 2를 반환합니다.
    // 문제 조건에 따라 괄호는 무조건 ] 또는 )로 주어지므로 이렇게 구현해도 충분합니다.
    return close == ']' ? 3 : 2;
}

 

📌정답 출력

위와 같은 과정을 끝까지 반복하고 나면 정답을 출력해 줄 것입니다.

 

다만 출력하기 전에 괄호 문자열이 유효한지 한 번 더 검증할 건데요,

모든 괄호의 짝이 맞았다면 스택에 더 이상 남는 괄호가 없어야 합니다.

그러나 앞선 과정이 정상적으로 실행되었더라도 문자열이 올바르지 않아서

스택에 아직 열린 괄호가 남아있을 가능성이 있습니다.

(() => 프로그램 실행 후 스택에 '('가 남는다.
(()[]()[ => 프로그램 실행 후 스택에 '(['가 남는다.
()[]()[[[ => 프로그램 실행 후 스택에 '[[['가 남는다.

 

그러므로 스택이 비어 있는지 확인하고 그렇다면 지금까지 구한 합계를, 그렇지 않다면 0을 출력할 것입니다.

System.out.println(st.isEmpty() ? answer : 0);

 

[제출 결과]

 

 

 

 

 

추가로 List의 역할을 배열로 대체한 코드도 함께 올립니다.

 

[✅ 정답 코드 - Stack과 배열 사용]

package stack;

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

public class Main_2504_Array {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int N = input.length();

        Stack<Character> st = new Stack<>();
        int[] sums = new int[N];
        int idx = -1;
        int answer = 0;

        for (int i = 0; i < N; i++) {
           char curr = input.charAt(i);

           if(curr == '(' || curr == '['){
               st.push(curr);
               sums[++idx] = 0;
           }else{
               if(st.isEmpty() || !isPair(st.peek(), curr)){
                   System.out.println(0);
                   return;
               }else{
                   st.pop();
                   int total = sums[idx];
                   int result = (total == 0 ? 1 : total) * getMult(curr);
                   if(--idx >= 0){
                       sums[idx] = sums[idx] + result;
                   }else{
                       answer += result;
                   }
               }
           }

        }

        System.out.println(st.isEmpty() ? answer : 0);
    }

    static int getMult(char close){
        return close == ']' ? 3 : 2;
    }

    static boolean isPair(char open, char close){
        if( (open == '(' && close == ')') || (open == '[' && close == ']') )
            return true;
        else
            return false;
    }
}

 

 

배열로 바꾸기 전과 성능상 큰 차이는 없었습니다.

---

 

코드와 관련된 피드백이나 질문이 있으시면 댓글 부탁드립니다.