[알고리즘] 괄호(백준9012번), 스택(stack), 실버4(silver4), 자바(java)

---

keyword : 문자열, stack, 스택
difficulty : 실버4
completion : ✅
notice :

---

괄호

📝 문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

예제 입력

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1

NO
NO
YES
NO
YES
NO

예제 입력 2

3
((
))
())(()

예제 출력 2

NO
NO
NO

---

🔍 정답

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

public class Main {  

    public static void main(String[] args) throws IOException {  

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int T = Integer.parseInt(br.readLine());  
        StringBuilder sb = new StringBuilder();  

        for (int i = 0; i < T; i++) {  
            int leftcnt = 0;  
            int rightcnt = 0;  
            char[] ch = br.readLine().toCharArray();  

            for (int j = 0; j < ch.length; j++) {  
                if (leftcnt >= rightcnt) {  
                    if (ch[j] == '(') leftcnt++;  
                    else rightcnt++;  
                } else break;  
            }  
            if (leftcnt == rightcnt) sb.append("YES" + "\n");  
            else sb.append("NO" + "\n");  
        }  
        System.out.println(sb);  
    }  
}

• 입출력값을 보고 분석을 해보니 YES가 출력되기 위한 조건이 2가지가 있었다.
  • 왼쪽 괄호와 오른쪽 괄호의 숫자가 같을 것
  • 오른쪽 괄호의 숫자가 더 클 때가 없을 것
    • 예시_( ) ) ( ) (
    • 예시처럼 괄호의 숫자는 같으나 오른쪽 괄호가 먼저 나오면 모양이 맞지 않는다.
• 괄호들을 char 배열에 넣은 뒤 왼쪽 괄호가 나오면 leftcnt를 오른쪽 괄호가 나오면 rightcnt를 세어줄 것이다.
• 중간에 rightcnt가 커지는 경우가 있다면 바로 조건문을 빠져나온다.
  • 이 경우 마지막 if문에서는 양쪽 괄호의 숫자가 맞지 않으므로 NO가 자동 입력된다.
• 반복문이 끝나면 각 괄호의 숫자를 세어주고 YES와 NO를 출력하면 된다.
• 처음에 StringBuilder를 사용하지 않아서, 그리고 반복문에서 rightcnt가 클 때 바로 반복문을 나오지 않고 sb.append("NO" + "\n")를 했을 때, 두 가지 경우에 출력초과가 나왔었다

 

• 이 문제는 대표적인 stack 문제라고 한다.
• stack으로는 한 번도 문제를 풀어본 적이 없어서 다른 사람의 풀이를 참고하기 위해 가져왔다.

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

public class Main {

public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

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

    for(int i = 0; i < T; i++) {
        sb.append(solve(br.readLine())).append('\n');
    }

    System.out.println(sb);
}

public static String solve(String s) {

    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 여는 괄호일 경우 스택에 넣는다.
        if (c == '(') {
            stack.push(c);
        }

        // 아래는 모두 닫는 괄호 일 경우들이다.
        // 스택이 비어있는 경우. 즉, 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
        else if (stack.empty()) {
            return "NO";
        }
        // 그 외의 경우 stack 원소를 pop 한다.
        else {
            stack.pop();
        }
    }

    /*
     * 모든 검사 마치고 스택에 잔여 요소가 있으면 여는 괄호가 많은 경우는 "NO" 
     * 스택이 비어있으면 온전한 수식이므로 "YES" 이다.
     */

    if (stack.empty()) {
        return "YES";
    } 
    else {
        return "NO";
    }
}
}