(2) [C++, Java, Python] 백준 No.9012 : 괄호

문제

풀이

방법1. 하나씩 짝을 찾는 방법                                   => O(N^2)의 시간복잡도
방법2. 스택을 이용하여 짝이 맞는지 확인하는 방법  => O(N)의 시간복잡도
방법3. 개수를 세는 방법                                         => O(N)의 시간복잡도, 스택을 사용하지 않아도 되므로 구현이 용이

 

# C++

#include <iostream>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    
    int N;
    string str;  // 입력을 받기위한 변수
    int cnt = 0; // 개수를 세기위한변수

    cin >> N;

    while (N--)
    {
        cin >> str;

        for (int i = 0; i < str.size(); i++)
        {
            if (str[i] == '(')
                cnt += 1;

            else if (str[i] == ')')
            {
                cnt -= 1;
                if (cnt < 0)
                    break;
            }
        }

        if (cnt == 0)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
            
        cnt = 0; // cnt 초기화
    }
}

# Java

import java.util.*;
import java.math.*;

public class Main {
    public static String isValid(String s) {
        s = s.trim();
        int n = s.length();
        int cnt = 0;
        for (int i=0; i<n; i++) {
            if (s.charAt(i) == '(') {
                cnt += 1;
            } else {
                cnt -= 1;
            }
            if (cnt < 0) {
                return "NO";
            }
        }
        if (cnt == 0) {
            return "YES";
        } else {
            return "NO";
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        while (n-- > 0) {
            System.out.println(isValid(sc.nextLine()));
        }
    }
}

# Python

import sys
r = lambda: sys.stdin.readline().strip()


def isValid(s):
    n = len(s)
    cnt = 0
    for x in s:
        if x == '(':
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            return "NO"
    if cnt == 0:
        return "YES"
    else:
        return "NO"

n = int(r())

for i in range(n):
    print isValid(r())