[BOJ] 백준 9012 괄호

9012 괄호

단계 별 문제 중 스택부분에 해당한다. 스택을 활용해서도 풀 수 있지만 스택의 개념만 차용해서 풀 수 있어서 재밌게 풀었던 것 같다. 생각보다 문제 푼 확률이 낮아 긴장을 하고 풀었지만, 풀어보니 그렇게 어렵지 않았던 것 같다. 스택의 개념을 알 수 있는 좋은 문제라고 생각한다. 같이 풀어보자.

문제

괄호 문제 는 괄호의 짝이 맞는 것을 VPC라고 부른다. 주어진 괄호가 VPC 조건을 만족하는가를 판단해 결과를 출력하는 문제이다. (VPC의 정의는 문제링크를 통해 자세히 보자)

아래 그림은 예제 입력과 출력의 결과이다. 그림과 같이, 괄호가 입력으로 주어지고 단순하게 판단을 하면 되는 문제이다.

괄호 예제

문제풀이

문제예제만 보더라도 스택 자료구조를 활용하면 되겠다는 생각이 들었을 것이다. 주어진 문자열을 문자별로 나눠 ( 기준으로 판단하면 된다.

( 일 경우 push
) 일 경우 pop

두 동작을 반복하면서 결과를 통해 stack 내 데이터가 남아 있거나, pop을 할 때, stack에 데이터가 없다면 NO를 출력하고 그 외는 YES를 출력하면 된다.

내가 풀었던 방식은 stack 구조는 필요없다 이다. 실질적으로 필요한 것은 stack에서 데이터 존재 유무를 판단하는 top요소이다. 따라서 ( 가 들어올 경우 top을 증가시켜 스택에 데이터가 있는 것처럼 만들고 ) 들어올 경우 스택에 데이터를 하나 제외하는 것처럼 만들었다.

위의 문제 풀이와 아래의 소스코드를 같이 보면서 생각해보자

#include <iostream>

using namespace std;

int main()
{
  int N;
  cin >> N;

  while(N--) {
    int top = 0;
    string tmp;
    cin >> tmp;

    for(int i = 0; i < tmp.size(); i++) {
      if (tmp[i] == '(') {
        top++;
      } else {
        top--;
        if (top < 0) {
          break;
        }
      }
    }

    if (top != 0) cout << "NO" << endl;
    else cout << "YES" << endl;
  }
}

다른 사람 풀이

다른 사람 풀이를 보고 인사이트를 얻으면 정리를 하고자한다. 다른사람들이 푼 풀이를 봤을 때, 상위권에 있는 분들은 top을 활용해서 푼 것을 확인했다. (나는 아직 쪼랩이다..)

다른 사람의 풀이를 보는 중 puts을 활용해 재밌게 출력했던 부분이 있어 정리하고자한다. 문제를 풀다보면 출력을 위해 아래와 같이 if, else 을 통해 출력을 해야되는 경우가 발생한다.

if (top != 0) cout << "NO" << endl;
else cout << "YES" << endl;

위와 같이 풀면 되긴 하지만, 좀 더 줄일 수 있는 방법 또는 좀 더 깔끔하게 할 수 있는 방법을 찾았다.

puts(top ? "NO" : "YES");

위의 코드와 같이, puts 문에 3항 연산자를 넣고 출력을 해주면 깔끔하게 풀 수 있다. (개인적으로 아름다운 출력이라 생각한다. 현업에서는 사용하면 욕을 먹겠지만 문제를 풀때 만큼은 위와 같이 푸는 것이 좋을 것 같다.)

괄호 스택 문제를 풀어보자

9012 괄호

문제

문제풀이

다른 사람 풀이