[백준 알고리즘] 9012번 괄호 (Python, Java)

 

<Python>

첫번째 코드 - 60ms

import sys
T = int(input())

for _ in range(T):
    line = sys.stdin.readline()
    bracket =[]
    cnt = 0
    for ch in line:
        if cnt < 0:
            break
        if ch =='(':
            bracket.append(ch)
            cnt += 1
        elif ch ==')':
            if len(bracket)>0:
                bracket.pop()
                cnt -= 1
            else:
                cnt = -1
                break

    if cnt == 0:
        print("YES")
    else:
        print("NO")

처음에는 단순히 스택만 생각해서 리스트를 만들고 append하고 pop하는 방식으로 구현했는데 뭔가 코드가 더러워져서 다시 짰다. 코드 길이도 훨씬 짧고 시간도 훨씬 짧게 나왔다 :)

 

두번째 코드 - 56ms

import sys
T = int(input())

for _ in range(T):
    line = sys.stdin.readline()
    cnt = 0
    for ch in line:
        if ch =='(':
            cnt += 1
        elif ch ==')':
                cnt -= 1
        if cnt < 0:
            print("NO")
            break
    if cnt == 0:
        print("YES")
    elif cnt>0:
        print("NO")

 

<Java>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++){
            String line = br.readLine();
            Stack stack = new Stack();
            boolean check = true;

            for(int j=0; j<line.length(); j++){
                if(line.charAt(j)=='(')
                    stack.push(0);
                else if(line.charAt(j)==')' && stack.size()>0)
                    stack.pop();
                else
                    check = false; // 사이즈가 0인데 pop하려는 경우
            }
            if(stack.size()==0 && check)
                System.out.println("YES");
            else //루프를 돌았는데 size가 0이 아닌경우 (괄호가 남은 경우)
                System.out.println("NO");
        }


    }
}

 

▼ 링크

https://www.acmicpc.net/problem/9012

9012번: 괄호