[알고리즘/백준] 4949 균형잡힌 세상(자바, 스택)

문제

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

풀이 코드

• 스택을 사용하여 풀이한다.
• 여는 괄호를 만나면 스택에 넣고, 닫는 괄호를 만나면 스택에서 꺼내 스택에서 꺼낸 여는 괄호와 짝이 맞는지 확인
• 균형 잡힌 문자열이 아닌 경우
  • 스택에서 꺼낸 여는 괄호가 닫는 괄호와 쌍이 맞지 않거나 스택이 비어있으면 균형잡힌 문자열이 아니다.
  • 탐색이 끝났음에도 불구하고 스택이 비어있지 않으면 여는 괄호 개수가 더 많아 괄호 짝이 맞지 않았다는 것이므로 균형잡힌 문자열이 아니다.

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));

        //StringBuilder를 사용하여 한번에 모아 출력함으로 실행시간 단축
        StringBuilder sb = new StringBuilder();

        while (true) {
            String s = br.readLine();

            //입력 종료 조건
            if (s.equals(".")) {
                break;
            }

            Stack<Character> stack =new Stack<>();
            boolean isBalance = true; //true이면 균형 잡힌 문자열

            for (char c : s.toCharArray()) {

                //여는 괄호이면 스택에 넣는다.
                if (c == '(' || c == '[') {
                    stack.push(c);
                }

                if (c == ')') {
                    //닫는 ) 괄호인데 스택이 비어있거나 pop한 값이 ( 이 아니면 균형이 맞지 않는 문자열
                    if (stack.isEmpty() || stack.pop() != '('){
                        isBalance = false;
                        break;
                    }
                }

                if (c == ']') {
                    //닫는 ] 괄호인데 스택이 비어있거나 pop한 값이 [ 이 아니면 균형이 맞지 않는 문자열
                    if (stack.isEmpty() || stack.pop() != '['){
                        isBalance = false;
                        break;
                    }
                }
            }

            //탐색이 종료되었지만, 스택이 비어있지 않다면 괄호 짝이 맞지 않아 균형이 맞지 않는 문자열
            if (!stack.isEmpty()) {
                isBalance = false;
            }

            sb.append(isBalance ? "yes" : "no").append("\n");
        }

        System.out.println(sb);
    }
}