[C++] 백준 9012번 풀이 (괄호)

- 문제 (9012번) : 괄호

• 링크 : https://www.acmicpc.net/problem/9012

• 입력받은 괄호문자열이 () 처럼 괄호의 모양이 바르게 구성되었는지 판별하는 문제. ( 올바른 구성이면 "YES", 그렇지 않으면 "NO" 출력 )

---

- 입력 및 출력

[입력]

• 첫째줄에 테스트케이스 개수 N 입력.
• 두번째줄부터 각 테스트 케이스의 괄호 문자열을 한줄에 입력.
  (괄호 문자열의 길이는 2 ≤ 길이 ≤ 50)

[출력]

• 각각의 테스트케이스마다 결괏값 출력. ( 아래의 사진 참고 )
• 올바른 괄호문자열이면 "YES", 그렇지 않으면 "NO" 출력
  <<<<<< 출력 예시 >>>>>>>

---

- 문제 풀이

• 이 문제는 data structure중에서 stack을 활용해 해결했다.

• 올바른 괄호 문자열이 되기 위해선 다음의 조건을 만족해야한다.

  1. 닫는 괄호( ")" ) 는 반드시 여는 괄호 ( "(" ) 뒤에 나와야한다.
     ( 이때 여는 괄호 ( "(" )의 개수 ≥ 닫는 괄호( ")" )의 개수 이어야한다. )
  2. 하나의 괄호문자열에 있는 여는 괄호 ( "(" )의 개수와 닫는 괄호( ")" )의 개수는 동일해야한다.
     ( 여는 괄호 ( "(" )의 개수 == 닫는 괄호( ")" )의 개수 )

• 이러한 조건을 고려하고자 stack을 사용해 해결한다.

  • 여는 괄호 ( "(" ) 만 stack에 push한다.
    
    
  • 닫는 괄호 ( ")" ) 를 입력받으면 stack에서 pop한다.
    - 이때 stack이 비어있다면 즉, 여분의 여는 괄호( "(" ) 가 하나도 없다면 결과가 바로 "NO" 가 된다. ( 조건 1에 의해 )
    
    
  • 입력받은 괄호문자열을 모두 검사한 후 stack이 비어있다면
    즉, 조건 2를 만족한다면 "YES" 출력, stack이 비어있지 않다면 "NO" 출력.

• 이번 괄호 문제의 핵심은 여는 괄호 ( "(" ) 만을 stack에 넣고,
  닫는 괄호는 ( ")" ) stack에 있는 여는 괄호를 짝을 맞춰 pop 하는 것이다.

---

- 최종 코드