[백준 9012] 괄호 (C#, C++) - soo:bak

작성일 :

문제 링크

9012번 - 괄호

설명

괄호 문자열이 올바른지 확인하는 문제입니다.

문자열은 ( 와 ) 만으로 구성되며, 괄호의 짝이 맞으면 올바른 괄호 문자열(VPS) 이라고 합니다.

올바른 괄호 문자열(VPS)의 조건

  1. 여는 괄호 ( 가 닫는 괄호 )보다 먼저 나와야 합니다.
  2. 모든 괄호가 짝이 맞아야 합니다.
  3. 중간에 닫는 괄호가 여는 괄호보다 많아지면 VPS가 아닙니다.

    예를 들어:

    (()()) → YES (올바른 VPS)

    ())( → NO (짝이 맞지 않음)

    ((() → NO (여는 괄호가 남음)

접근법

문제 해결을 위해 스택(Stack) 자료구조를 사용합니다.

  1. 문자열을 한 글자씩 확인합니다.
  2. 여는 괄호 (를 만나면 스택에 저장합니다.
  3. 닫는 괄호 )를 만나면 스택에서 하나를 꺼냅니다.
  4. 닫는 괄호가 나왔는데 스택이 비어있으면 VPS가 아닙니다.
  5. 문자열을 모두 확인한 후 스택이 비어있으면 VPS입니다.

풀이과정 예시

문자열: "(())()"

  • ( → 스택: [()]
  • ( → 스택: [(, ()]
  • ) → 스택에서 ( 제거 → [()]
  • ) → 스택에서 ( 제거 → 스택: []
  • ( → 스택: [()]
  • ) → 스택에서 ( 제거 → 스택: []

    최종적으로 스택이 비어 있으므로 VPS입니다. (YES)




Code

[ C# ] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Solution {
  class Program {

    static void Main(string[] args) {

      var sb = new StringBuilder();
      var t = int.Parse(Console.ReadLine()!);

      Enumerable.Range(0, t).ToList()
        .ForEach(_ => {
          var str = Console.ReadLine()!;
          var stack = new Stack<char>();
          var isValid = true;

          foreach (char ch in str) {
            if (ch == '(') stack.Push(ch);
            if (ch == ')') {
              if (stack.Count == 0) { isValid = false; break; }
              else stack.Pop();
            }
          }

          sb.AppendLine(isValid && stack.Count == 0 ? "YES" : "NO");
        });

      Console.Write(sb);
    }
  }
}



[ C++ ] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>

using namespace std;
typedef stack<char> stc;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t; cin >> t;
  while (t--) {
    string str; cin >> str;

    stc s;
    bool isValid = true;
    for (size_t i = 0; i < str.length(); i++) {
      if (str[i] == '(') s.push(str[i]);
      if (str[i] == ')') {
        if (s.empty()) isValid = false;
        else s.pop();
      }
    }
    if (isValid && s.empty()) cout << "YES\n";
    else cout << "NO\n";
  }

  return 0;
}

이 블로그의 다른 글