[자료구조] 백준 - 균형잡힌 세상

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

4949번: 균형잡힌 세상

 

-문제해설

와 처음에 되게 복잡하게 풀었었다. 게시판에 나와있는 여러 반례들은 모두 맞는데 채점하면 틀렸다고 나와서 대대적인 수정을 했다. 논리는 비슷한데 수정후에 정답을 맞췄다...  진짜 반례 찾느라 너무 힘들었다.

 

스택을 사용해야지 풀기 편한 문제이다.

먼저 출력되어야할 값을 StringBuffer에 담아주고 . 이 입력되면 한꺼번에 출력시켜서 메모리를 효율적으로 사용한다.

 

입력값을 문자열로 받은 뒤 반복문에서 문자열.toCharArray() 메소드를 이용해서 문자배열로 순회한다.

이때 각 문자를 s라고 한다.

 

s가 소괄호, 대괄호 열기 (, [ 라면 스택에 s를 추가한다.

s가 소괄호 닫기 ) 인데 스택에 있는 값이 소괄호 열기 ( 가 아니라면 ans 문자열에 "no"를 저장하고 반복문을 빠져나온다.

이때 flag라는 판단값을 1로 설정했는데 괄호열기 없이 괄호 닫기가 나온경우에도 ans에 "no"저장되게하기 위해서 추가하였다.

만약 스택에 있는 값이 소괄호 열기 ( 였다면 해당 스택을 pop해주고 계속 반복문을 순회한다.

 

대괄호도 마찬가지이다.

 

 

파이썬 풀이는 백준의 hyun0404woo님의 코드를 참고했다.

 

 

-자바

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

public class BJ4949 {

	public static void main(String[] args) throws IOException {	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		String line = "";
		
	    
                //.나올 때까지 반복
		while( true ) {
			Stack<Character> stack = new Stack<Character>();
			String ans = "no";   //최종 결과값
			int flag = 0;//괄호열기없이 괄호닫기 나왔을 경우 ans에 "no"를 저장하기 위한 판단값	
			
			line = br.readLine();
                        //.이면 종료
			if( line.equals(".") ) break;
			
			//문자열을 문자배열로 바꾼 뒤 순회
			for( char s : line.toCharArray() ) {
				
				//소괄호 또는 대괄호 열기 등장하면 스택에 삽입
				if( s=='(' || s=='[' ) stack.add( s );
				
				//소괄호 닫기 등장할 경우
				else if( s == ')' ) {
					//스택이 비워져있거나 스택 최근값이 (가 아닐 경우
					if( stack.isEmpty() || stack.peek() != '(' ) {
						ans = "no";
						flag = 1;
						break;	//바로 반복문 종료
					
					//스택의 최근값이 소괄호 열기이면 해당 스택값을 제거
					} else if( !stack.isEmpty() && stack.peek() == '(' ) stack.pop(); 
				} 
				//대괄호 닫기 등장할 경우
				else if( s == ']' ) {
					//스택이 비워져있거나 스택 최근값이 (가 아닐 경우
					if( stack.isEmpty() || stack.peek() != '[' ) {
						ans = "no";
						flag = 1;
						break;	//바로 반복문 종료
					
					//스택의 최근값이 대괄호 열기이면 해당 스택값을 제거
					} else if( !stack.isEmpty() && stack.peek() == '[' ) stack.pop(); 
				}
			}//for end
			
			if( !stack.isEmpty() || flag == 1 ) ans = "no";
			else if( flag != 1 ) ans = "yes";
			
			sb.append( ans+"\n" );
			
		}//while end
		
		System.out.println( sb );
	}
}

 

-파이썬

def solve( line ):
    stack = []
    for i in line:
        if i in "([": 
            stack.append( i )
        elif i == ")":
            if not stack or stack.pop() != "(":
                print( "no" )
                break
        elif i == "]":
            if not stack or stack.pop() != "[":
                print( "no" )
                break
        elif i == ".":
            if stack: 
                print( "no" )
                break
            else:
                print( "yes" )
                break

if __name__ == "__main__":
    import sys
    while( True ):
        line = sys.stdin.readline().rstrip()
        if line == ".": break
        else: solve( line )