백준 9012번 - 괄호 / Java

문제

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

9012번: 괄호

올바른 괄호 문자열인지 확인하는 문제.

상당히 유명한 문제이다.

 

일단 이 문제의 가장 유명한 풀이 방법은 스택의 LIFO성질을 이용한 풀이이다. 다른 방법도 있지만 필자는 스택 활용을 연습하기 위해서 스택으로 풀었다.

 

 

알고리즘

1. 괄호문자열을 입력받는다

2. String.charAt(index) 메서드를 이용해서 문자 하나하나를 탐색한다

3. '('  경우 스택에 push ')'  일경우에는 pop. 이때 ')' 가 입력 됐을 경우에 스택이 비어있다면 이미 올바르지 않은 괄호 문자열이기 때문에 ')'을 그대로 푸시하고 반복문에서 나온다.

4. 마지막에 스택이 비어있다면 올바른괄호문자열, 비어있지 않다면 올바르지 않은 괄호 문자열 

※ 다른 풀이 방법 (소스코드 기재x)

1. int 형 변수를 하나 선언해서 0으로 초기화한다

2. '('가 입력되면 ++, ')'가 입력되면 --, 이때 변수의 값이 0일 때 ')'가 입력된다면 올바르지 않은 괄호 문자열 이기 때문에 break

3. 마지막에 변수의 값이 0이면 올바른 괄호 문자열, 0이아니면 올바르지 않은 괄호문자열

소스코드 및 설명

 

1,2,3,4, 번 알고리즘

        for(int i=0;i<n;i++) {
            String str = scan.nextLine(); // 괄호문자열을 입력받고
            for(int j=0;j<str.length();j++) {
                if(str.charAt(j)=='(') { // 열린괄호면
                    stack.push(str.charAt(j)); // 스택에 넣어준다
                }
                else {
                    if(!stack.isEmpty()) { // 스택이비어있지않으면 열린괄호열이 들어있는것
                        stack.pop(); // 빼버리고
                    }
                    else { // 스택이 비어있는데 닫힌괄호가들어오면 올바르지 않은 괄호
                        stack.push(')'); // 마지막 확인작업을 위해 추가하고
                        break; // 시간절약을 위한 break
                    }
                }
            }
            if(stack.isEmpty()) { // 스택이 비어있다면
                answer.add("YES"); // 올바른괄호
            }
            else {
                answer.add("NO"); 
            }
            stack.clear(); // 다음 테스트케이스를위해 스택 정리
        }
        for(String s : answer) {
            System.out.println(s);
        }
    }

 

전체 소스코드

import java.util.*;
/*
 * BOJ 9012
 * 2020.01.15
 * Hyeonseong
 */
public class BOJ9012 {
 
    public static void main(String[] args) {
        Solution s = new Solution();
        s.solution();
    }
}
class Solution{
    
    int n; // 테스트케이스 수
    ArrayList<String> answer; // 정답
    Solution(){
        answer = new ArrayList<String>();
    }
    public void solution() {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        scan.nextLine();
        Stack<Character> stack = new Stack<Character>();
        for(int i=0;i<n;i++) {
            String str = scan.nextLine(); // 괄호문자열을 입력받고
            for(int j=0;j<str.length();j++) {
                if(str.charAt(j)=='(') { // 열린괄호면
                    stack.push(str.charAt(j)); // 스택에 넣어준다
                }
                else {
                    if(!stack.isEmpty()) { // 스택이비어있지않으면 열린괄호열이 들어있는것
                        stack.pop(); // 빼버리고
                    }
                    else { // 스택이 비어있는데 닫힌괄호가들어오면 올바르지 않은 괄호
                        stack.push(')'); // 마지막 확인작업을 위해 추가하고
                        break; // 시간절약을 위한 break
                    }
                }
            }
            if(stack.isEmpty()) { // 스택이 비어있다면
                answer.add("YES"); // 올바른괄호
            }
            else {
                answer.add("NO"); 
            }
            stack.clear(); // 다음 테스트케이스를위해 스택 정리
        }
        for(String s : answer) {
            System.out.println(s);
        }
    }
}