lango

찍먹? 부먹?
난 부먹 개발자.

1 minute read



자세한 입출력 테스트케이스는 문제 링크를 참고하자.



문제 풀이

이번 문제는 주어지는 괄호문자열의 짝이 맞는지를 확인해야 한다.
스택을 활용하면 단일 괄호 문자열의 짝이 맞는지 쉽게 구할 수 있다.


아이디어 도출

  • 주어지는 괄호 문자열을 순회하며 여는 괄호 “(“가 주어지면 스택에 삽입하고 닫는 괄호 “)”가 주어지면 스택에서 추출한다.
    • 이 때, 닫는 괄호가 나오면 스택에서 추출하는데, 스택이 비어있는 상태에서 닫는 괄호가 나올 수 있으니 try/catch문으로 EmprtyStackException을 처리하여 예외 발생시에는 짝이 맞지 않음으로 간주하고 NO를 출력한다.
  • 괄호의 짝이 맞는다면 스택이 비어있으면 된다. 스택이 비어있다면 YES 아니라면 NO를 출력한다.


바로 코드를 작성해보자.

1

int T = Integer.parseInt(br.readLine());

T개의 테스트케이스를 갯수를 입력받는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

for(int i=0; i<T; i++) {
    Stack<Character> st = new Stack<>();
    String bracketList = br.readLine();
    try {
        for(int j=0; j<bracketList.length(); j++) {
            if(bracketList.charAt(j) == '(') st.push('(');
            else st.pop();
        }

        if(st.empty()) bw.write("YES"+"\n");
        else bw.write("NO"+"\n");
    } catch(EmptyStackException e) {
        bw.write("NO"+"\n");
    }
}

T개의 단일 괄호 문자열을 줄마다 입력받는다.

  1. 이 때 문자열마다 스택에 담아 처리하고 짝검증을 해야하기에 줄 단위로 스택을 새로 생성한다.
  2. 그리고 try/catch문 안에서 여는 괄호 “(“가 나오면 스택에 삽입하고, 닫는 괄호 “)”가 나오면 스택에서 추출한다.
  3. try/catch문 안에서 여는 괄호와 닫는 괄호의 짝을 검사하는데, 닫는 괄호가 먼저 나올 경우
    스택이 비어있을 수도 있기에 스택이 비어있을 때 pop연산을 할 경우 EmptyStackException를 통해 제어할 수 있도록 한다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

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

        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            Stack<Character> st = new Stack<>();
            String bracketList = br.readLine();
            try {
                for(int j=0; j<bracketList.length(); j++) {
                    if(bracketList.charAt(j) == '(') st.push('(');
                    else st.pop();
                }

                if(st.empty()) bw.write("YES"+"\n");
                else bw.write("NO"+"\n");
            } catch(EmptyStackException e) {
                bw.write("NO"+"\n");
            }
        }

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

회고

  • 괄호 문자열 관련 문제는 대부분 스택을 활용하여 푸는 것이 대중적인 풀이방식으로 알고 있는데, EmptyStackException을 처리하지 않고도 풀어봐야겠다.

You may also enjoy