[백준] 4949번 균형잡힌 세상(JAVA)

문제

- 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단

- 문자열에 포함되는 괄호는 소괄호("()")와 대괄호("[]")로 2종류

- 문자열이 균형을 이루는 조건은 아래와 같음

   1. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 함

   2. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 함

   3. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재

   4. 모든 괄호들의 짝은 1:1 매칭만 가능. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않음

   5. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 함

- 입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어옴

- 문자열이 균형을 이루고 있으면 "yes" / 아니면 "no" 출력

 

해결방법

괄호가 짝을 이루고 있는지 판단하면 되기 때문에 stack에 괄호를 쌓아 비교할 수 있도록 하였다. 문자가 입력되는 것이라면 pass하고 괄호를 만났을 때, stack에 쌓을 수 있도록 하였다. 스택이 비었을 때, 입력되는 값이 왼쪽 괄호라면 바로 push()할 수 있도록 하였고, 오른쪽 괄호라면 no를 출력할 수 있도록 하였다. 그리고 스택에 무언가 담겨있을 때, 왼쪽 괄호를 만나면 계속해서 쌓아주고 오른쪽 괄호를 만나면 스택에 맨 위에 있는 것을 pop()하여 짝이 맞는지 확인해주었다.

 

코드

import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            String s = br.readLine();
            if(s.equals(".")) break;				// 입력받은 문자열이 종료조건이면 종료
            Stack<Character> stack = new Stack<>();		// 괄호를 담을 stack
            String result = "yes";

            for(int i = 0; i<s.length(); i++){
                char c = s.charAt(i);				// 입력받은 문자열을 한글자씩 검색
                // 괄호라면
                if(c == '(' || c == ')' || c == '[' || c == ']'){
                    // stack이 비어있다면
                    if(stack.isEmpty()){
                    	// 입력받은게 왼쪽 괄호가 아니라면 no 출력
                        if(c == ')' || c==']') {
                            result = "no";
                            break;
                        }
                        // 왼쪽 괄호라면 stack에 push()
                        stack.push(c);
                    }
                    // stack이 비어있지 않다면
                    else{
                        if(c == '(' || c == '[') stack.push(c);		// 왼쪽 괄호라면 push()
                        if(c == ')'){					// 오른쪽 소괄호라면
                            char before = stack.pop();			// 이전 것 pop()
                            if(before != '(') result = "no";		// pop()한 것이 소괄호가 아니라면 no 출력
                        }
                        else if(c == ']'){				// 오른쪽 대괄호라면
                            char before = stack.pop();			// 이전 것 pop()
                            if(before != '[') result = "no";		// pop()한 것이 대괄호가 아니라면 no 출력
                        }
                    }
                } 
                // 글자라면
                else continue;		// 다음 글자
            }

            if(!stack.isEmpty()) result = "no";

            System.out.println(result);
        }

        br.close();
    }
}