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

문제링크:

4949번: 균형잡힌 세상

 

 

문제:

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

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

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

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

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

 

 

입력:

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.

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

 

출력:

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

 

문제 이해:

이 문제는 한 문장을 입력했을때 소괄호나 대괄호 쌍이 일치하면 yes,

일치하지 않으면 no를 출력하는 것이다. 이때 괄호가 없는 경우도 yes로 간주된다.

즉 예제 입력 1에서 첫번째 문장을 봣을때

So when I die (the [first] I will see in (heaven) is a score list).

괄호만 추출하면 '( [ ] ( ) )' 로 성립되어 yes가 출력된다.

만약 '[ ] ( ) )' 인경우는 마지막 ' )' 에서 쌍이 성립되지 않기에 no가 출력되는 것이다.

 

구현 방향:

괄호 문제를 해결할 때는 스택(Stack)을 떠올리면 접근이 쉬워진다.

구현은 다음과 같은 흐름으로 진행된다:

1. 여는 괄호가 등장하면 스택에 push한다.
2. 닫는 괄호가 등장하면 스택에서 pop을 수행한 후, 꺼낸 괄호와 현재 닫는 괄호가 쌍을 이루는지 확인한다.
   • 쌍이 맞지 않으면 올바르지 않은 괄호열이다.
3. 모든 문자를 처리한 뒤에도 스택에 여는 괄호가 남아 있다면, 이 역시 쌍이 맞지 않다는 뜻으로 실패한 경우이다.

즉, 스택을 활용하여 괄호의 짝을 검사함으로써 간결하고 정확한 구현이 가능하다. 

예를 들어 추가 설명을 하면 다음과 같다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

정답코드:

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

public class Main {

    public static void findYesOrNo(StringBuilder sb){
        Stack<Character> stack= new Stack<>();
        int i=0;
        boolean yesOrNo=true;
        //판별 시작
        while (i!=sb.length()-1){

            //해당 문자열이 여는 소괄호나, 여는 대괄호면
            if(sb.charAt(i)=='[' || sb.charAt(i)=='('){
                stack.push(sb.charAt(i)); //push
            }

            //해당 문자열이 닫는 소괄호나, 닫는 대괄호면
            if(sb.charAt(i)==']' || sb.charAt(i)==')'){
                //여는 괄호가 없는데 닫힌 괄호가 먼저나오면 매칭x
                if(stack.isEmpty()){
                    yesOrNo=false;
                    break;
                }
                char c= stack.pop();

                //닫는 대괄호인데 stack top이 여는 대괄호이면 성공
                if(sb.charAt(i)==']' && c=='['){
                    yesOrNo=true;
                }
                if(sb.charAt(i)==']' && c!='['){
                    yesOrNo=false;
                    break;
                }


                //닫는 소괄호인데 stack top이 여는 소괄호이면 성공
                if(sb.charAt(i)==')' && c=='('){
                    yesOrNo=true;
                }
                if(sb.charAt(i)==')' && c!='('){
                    yesOrNo=false;
                    break;
                }
            }
            i++;
        }

        //스택이 비어있고 모두 매칭이 된경우
        if(yesOrNo && stack.isEmpty())System.out.println("yes");
        else System.out.println("no");
    }

    public static void main(String[] args) throws IOException {
        StringBuilder sb;

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        while (true){
            String str= br.readLine(); //문장 입력
            sb=new StringBuilder(str);

            //종료 조건
            if(str.equals(".")){
                break;
            }

            findYesOrNo(sb);

        }
    }
}

 

 

마무리하며:

스택을 사용해 괄호 짝의 규칙만 잘 이해하고 있다면 구현 자체는 어렵지 않은 문제이다.

하지만 작성자는 초기에 문자열 전체를 순회한 후, 스택에 남아 있는 여는 괄호를 처리하는 로직을 누락하여 한 차례 오답을 경험했다.

 

이 경험을 통해 끝까지 꼼꼼하게 예외 상황을 고려하는 것의 중요성을 다시 한 번 깨달을 수 있었다.