[백준, 9012번] 괄호 (문자열, 스택, Java)

문제설명

입력 & 출력

나의 풀이

이번 "백준 - 괄호" 문제는 스택을 사용하기에 적합한 문제입니다. 주어진 괄호 문자열이 올바른 괄호 문자열(VPS)인지를 판단하는 문제입니다.

 

주어진 문자열에서 괄호가 올바르게 짝을 이루는지, 즉 열린 괄호 '(', 닫힌 괄호 ')'가 올바르게 짝을 이루고 있는지 확인하는 문제입니다.

 

1번 째 풀이 -> 실패

public class BOJ9012 {
    static Stack<Character> stack;
    static StringTokenizer token;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            token = new StringTokenizer(br.readLine());
            stack = new Stack<>();

            char[] line = token.nextToken().toCharArray();
            for (int j = 0; j < line.length; j++) {
                if(!stack.isEmpty() && stack.peek() != line[j]){
                    stack.pop();
                }else {
                    stack.push(line[j]);
                }
            }
            if(stack.size() == 0){
                sb.append("YES").append("\n");
            }else {
                sb.append("NO").append("\n");
            }
        }

        System.out.println(sb.toString().trim());
    }
}

 

잘못된 풀이에서는 stack.peek()로 열린 괄호와 닫힌 괄호의 짝을 확인하고, 조건에 맞으면 stack.pop()을 실행하고, 그렇지 않으면 stack.push(line[j])를 수행합니다.

 

스택이 비어 있는 상태에서 ')'가 등장할 때 stack.peek()를 호출하면 스택 언더플로우는 방지했지만 논리적으로 VPS가 아님에도 불구하고 해당 )를 푸시하게 됩니다.

 

 닫힌 괄호 )는 항상 스택에서 열린 괄호와 짝을 맞춰야만 하며, 짝을 맞추지 못하는 경우 VPS가 아닙니다.

 

2번 째 풀이 -> 성공

• stack.peek() == ')' && line[j] == '(' 조건은 불필요

1. 여는 괄호는 스택에 무조건 쌓임 여는 괄호"("가 등장하면 조건 없이 스택에 쌓이므로, 특정 조건으로 따로 확인할 필요가 없습니다.
2. 닫는 괄호는 스택을 검사하여 처리됨 닫는 괄호")"가 등장했을 때, 스택이 비어 있는지 확인하거나, 맨 위에 여는 괄호"("가 있는지 검사해 쌍을 맞추기 때문에 이미 필요한 처리가 끝납니다.
3. 닫는 괄호 뒤에 여는 괄호가 나오는 경우도 기본 동작으로 처리 가능 닫는 괄호 뒤에 여는 괄호가 나오는 상황은 다음과 같이 처리됩니다.
   • 닫는 괄호는 스택의 맨 위 요소(()와 쌍을 맞추어 제거합니다.
   • 이후에 나오는 여는 괄호는 스택에 새로 쌓입니다. 즉, 추가적인 조건 없이도 정상적으로 처리됩니다.

즉, stack.peek() != line[j] 조건은 여는 괄호와 닫는 괄호가 일치하지 않는지 검사하려는 의도가 있지만, 실제로는 stack.pop()으로 짝을 맞추면 자연스럽게 일치하는 괄호만 처리됩니다.

 

풀이의 아이디어는 간단합니다.

 

각 테스트 케이스에 대해 문자열을 읽고, stack을 사용하여 여는 괄호 "("는 스택에 푸시하고, 닫는 괄호 ")"는 스택에서 꺼내어(pop) 짝을 맞춥니다.

 

만약 닫는 괄호 )가 나오면, 스택이 비어 있으면 짝을 맞출 여는 괄호가 없으므로 isVps를 false로 설정하고 반복을 종료합니다.

 

반복이 끝날 때 stack.isEmpty()가 false라면, 여는 괄호가 남아있는 상태이므로 이 또한 "NO"로 처리합니다.

 

---

 

• 1번 째 코드 : 열린 괄호와 닫힌 괄호만 고려한 코드
• 2번 째 코드 : 1번째 풀이를  닫힌 괄호 )는 항상 스택에서 열린 괄호와 짝을 맞추도록 수정한 뒤 제출한 코드

[자료구조 JAVA] 스택 Stack 컬렉션 알아보기 (1/2)