[JAVA / 자바] 백준 4949번 - 균형잡힌 세상

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호("()")와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형 잡힌 문자열인지 아닌지를 판단해보자.

---

입력

하나 또는 여러 줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

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

---

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

---

 

---

문제 접근 방법

이번 문제는 백준 9012번 - 괄호 문제와 유사한 응용문제이다.

이번 문제는 입력으로 들어오는 문자열에서 괄호의 짝이 맞는지 확인하는 문제이다.

따라서 문자열에서 문자는 전부 무시해주고 괄호만 남겨서 괄호만 따져주면 된다. (이때, 괄호는 소괄호('(', ')')와 대괄호('[', ']')만 입력으로 들어온다.)

그렇다면 한 줄을 통째로 문자열에 저장하고, 문자열. charAt(인덱스) 함수를 사용하여 괄호만을 찾아 여는 괄호('(', '[')가 나오면 스택에 push 해주고, 닫는 괄호(')', ']')가 나오면 pop을 해줘서 괄호의 짝이 맞으면 (즉, 대괄호의 닫는 괄호가 나와서 스택에 pop을 했더니 대괄호의 여는 괄호가 리턴) 문장이 끝날 때까지 문자열이 균형을 이루고 있는지 아닌지 판단을 하고, 만약 짝이 맞지 않으면(대괄호의 닫는 괄호가 나와서 스택에 pop을 했더니 소괄호의 여는 괄호가 나온다거나, 스택이 비어있는 경우 등) 이미 문자열의 균형이 맞지 않으므로 판독을 중단하고 "no"를 출력해준다.

이때, 주의할 점은 문자열이 아무런 입력 없이 공백만 온다거나, 아무것도 입력되지 않는 경우 "yes"라고 판단할 수 있어야 한다. 따라서 나는 이 경우엔 스택에 push도, pop도 하지 않고 그냥 판독이 끝나므로 자동적으로 "yes"라 출력될 수 있도록 코드를 작성할 것이다.

(나는 flag라는 boolean형의 판독기(?)를 만들어 균형이 맞는지 아닌지 판독하는 과정에서 문제가 있었는지 아닌지 판단해서 결괏값을 출력할 때 조건문으로 활용하였다.)

---

JAVA 코드 풀이

- BufferedReader + BufferedWriter

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

public class Main {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String line = br.readLine();
        Stack<Character> parenthesis = new Stack<>();
        boolean flag;
        while(!line.equals(".")){
            flag = true;
            for(int i=0; i<line.length(); i++){
                if(line.charAt(i) == '(' || line.charAt(i) == '[')
                    parenthesis.push(line.charAt(i));
                else if(line.charAt(i) == ')'){
                    if(parenthesis.isEmpty() || parenthesis.peek() != '('){
                        flag = false;
                        break;
                    }
                    else
                        parenthesis.pop();
                }
                else if(line.charAt(i) == ']'){
                    if(parenthesis.isEmpty() || parenthesis.peek() != '['){
                        flag = false;
                        break;
                    }
                    else
                        parenthesis.pop();
                }
            }
            if(parenthesis.isEmpty() && flag)
                bw.write("yes\n");
            else
                bw.write("no\n");
            parenthesis.clear();
            line = br.readLine();
        }
        bw.close();
    }
}

- Scanner + System.out.println()

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        String line = input.nextLine();
        Stack<Character> parenthesis = new Stack<>();
        boolean flag;
        while(!line.equals(".")){
            flag = true;
            for(int i=0; i<line.length(); i++){
                if(line.charAt(i) == '(' || line.charAt(i) == '[')
                    parenthesis.push(line.charAt(i));
                else if(line.charAt(i) == ')'){
                    if(parenthesis.isEmpty() || parenthesis.peek() != '('){
                        flag = false;
                        break;
                    }
                    else
                        parenthesis.pop();
                }
                else if(line.charAt(i) == ']'){
                    if(parenthesis.isEmpty() || parenthesis.peek() != '['){
                        flag = false;
                        break;
                    }
                    else
                        parenthesis.pop();
                }
            }
            if(parenthesis.isEmpty() && flag)
                System.out.println("yes");
            else
                System.out.println("no");
            parenthesis.clear();
            line = input.nextLine();
        }
    }
}

코드 실행 결과

BufferedReader + BufferedWriter 코드 실행 결과

Scanner + System.out.println() 코드 실행 결과

---

후기

이번 문제는 이전에 9012번을 풀었어서 그런지 문제를 보자마자 바로 풀 수 있었다. 괄호의 짝을 맞추는 문제는 스택을 활용하면 쉽게 해결이 가능하다고 생각한다. (아직 어려운 괄호 문제를 풀어보지 않아서 이렇게 생각하는 것일 수도 있다.)

---

문제 원본

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