[백준]9012_괄호_자바

9012번: 괄호

들어가기 앞서

이 문제는 스택을 이용하면 쉽게 풀 수 있다.

요점은 ( 과 ) 짝을 맞추는 것인데, 이 짝을 맞출려면 (에 대한 정보를 저장해야 한다.

제일 최근 (과 )를 매칭해야 하는데, 이런 상황에선 스택을 쓰면 된다.

처음엔 스택 2개를 사용해서 풀었으나, 통과시키고 보니까 굳이 두 개를 만들 필요가 없다는 것을 깨달아서 수정했었다.

코드

public class 백준9012_괄호 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader= new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
        int t = Integer.parseInt(bufferedReader.readLine());
        while (t-->0){
            String ps = bufferedReader.readLine();
            boolean error = false;
            for (var c : ps.toCharArray()){
                if (c == ')' ){
                    if (stack.isEmpty()){
                        error = true;
                        break;
                    }
                    stack.pop();
                    continue;
                }
                stack.push(c);
            }
            if (!stack.isEmpty() || error){
                System.out.println("NO");
            }else {
                System.out.println("YES");
            }
            stack.clear();
        }
    }
}

풀이

스택엔 ( 문자만 넣는다.

그리고 )가 판별이 됐을 때, 스택에서 (를 pop한다.

이때, 스택이 비어있는데 )이 판별이 됐을 땐, 에러로 간주하고 boolean 값을 true로 바꾸고 문자열 탐색을 중단하고 NO를 출력한다.

짝에 맞는 (가 없으므로 이는 반드시 VPS가 아니다.

 

모든 과정을 거쳤을 때, 스택이 비어있다는 것은 모든 짝을 맞춰서 진행이 됐다는 뜻이므로 YES를 출력한다.

만약, 스택이 비어있지 않다는 것은 (의 개수가 )보다 많은 경우이므로, NO를 출력한다.

 

다음은 입력에 따른 스택 예시이다. 

1. 첫 번째 입력: (())()

(	[ ( ]	여는 괄호 추가
(	[ (, ( ]	여는 괄호 추가
)	[ ( ]	닫는 괄호 -> 스택에서 하나 제거
)	[]	닫는 괄호 -> 스택에서 하나 제거
(	[ ( ]	여는 괄호 추가
)	[]	닫는 괄호 -> 스택에서 하나 제거

• 최종 상태: stack = [], error = false
  → 출력: YES

2. 두 번째 입력: (()))

(	[ ( ]	여는 괄호 추가
(	[ (, ( ]	여는 괄호 추가
)	[ ( ]	닫는 괄호 -> 스택에서 하나 제거
)	[]	닫는 괄호 -> 스택에서 하나 제거
)	[] -> error = true	닫는 괄호 -> 스택 비어있음 → 에러 발생

• 최종 상태: stack = [], error = true
  → 출력: NO

3. 세 번째 입력: (()(()

(	[ ( ]	여는 괄호 추가
(	[ (, ( ]	여는 괄호 추가
)	[ ( ]	닫는 괄호 -> 스택에서 하나 제거
(	[ (, ( ]	여는 괄호 추가
(	[ (, (, ( ]	여는 괄호 추가
)	[ (, ( ]	닫는 괄호 -> 스택에서 하나 제거

• 최종 상태: stack = [ ( ], error = false
  → 스택이 비어있지 않음 → 출력: NO