[자료구조] 백준 - 괄호

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

9012번: 괄호

 

-문제해설

저번에 풀었던 균형잡힌 세상의 쉬운버전이다. 테스트케이스 수인 t를 입력받고 t만큼 괄호가 있는 문자열을 입력받는다.

() 괄호 쌍이 맞을 경우 YES, 틀릴 경우 NO를 출력하면 되는 문제이다.

 

t만큼 반복되는 반복문 안에서 입력받은 문자열 line을 매개변수로 하는  chkVps( line ) 메소드를 호출한다.

이 메소드에서는 입력받은 문자열 line을 문자배열로 바꾼 뒤 순회하는 반복문이 있고

반복문 안에서는 문자 s가 괄호 열기일 경우 스택에 저장,

스택이 비워져있고 s가 괄호 닫기일 경우 곧바로 NO반환

스택이 비워져있지 않고 s가 괄호 닫기일 경우 스택의 최근값을 pop시킨다. 왜냐하면 최근스택값은 괄호 열기이기 때문이다.

 

그렇게해서 반복문이 종료된 후 스택이 비워져있으면 YES반환, 아니면 NO를 반환한다.

 

테스트케이스 반복문이 모두 끝나면 최종적으로 sb를 출력한다.

 

 

파이썬도 자바와 똑같이 풀었다.

 

 

-자바

package dataStructure;

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

public class BJ9012 {
	private static String chkVps(String line) {
		Stack<Character> st = new Stack<Character>();	//스택사용
		
		//매개변수인 line문자열을 문자배열로 바꾼 뒤 순회
		for( char s : line.toCharArray() ) {
			
			//문자s가 괄호열기라면 스택에 s 추가
			if( s=='(' ) st.add( s );
			
			//그 외 스택이 비워져있고 s가 괄호 닫기라면 바로 NO를 반환
			else if( st.isEmpty() && s==')' ) return "NO";
			
			//그 외 스택이 비워져있지 않고 s가 괄호닫기라면 스택의 최근값 비우기
			else if( !st.isEmpty() && s==')' ) st.pop();
		}
		
		//스택이 비워져있으면 PVS이므로 YES, 아니면 NO를 반환
		if( st.isEmpty() ) return "YES";
		else return "NO";
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt( br.readLine() );
		StringBuffer sb = new StringBuffer();
		
		for( int i=0; i<t; i++ ) {
		
			//stringbuffer에 각 줄의 결과값을 한꺼번에 저장해서 출력
			//chkVps라는 메소드를 호출하고 반환값을 sb에 append
			sb.append( chkVps( br.readLine() )+"\n" );
		}
		System.out.println( sb );
	}
}

 

 

-파이썬

def chkVps( line ):
    st = []
    for i in line:
        if i in "(": st.append( i )
        elif not st and i == ")": return "NO"
        elif st and i == ")": st.pop()
        
    if not st: return "YES"
    else: return "NO"

if __name__ == "__main__":
    import sys
    line = sys.stdin.readline
    
    t = int( line() )
    sb = ""
    for _ in range( t ):
        sb += chkVps( line() )+"\n"
        
    print( sb )