[ 백준 4949번 문제 ] 균형잡힌 세상 - JAVA

이번 글에서는 4949번 문제를 통해 스택을 활용,
괄호의 균형을 맞춰완벽한 문장을 나타내 보자.

---

 

 

문제 핵심

• 문자열은 ( ),  [ ] 이 두 소괄호와 대괄호가 짝을 이루어야 한다.
• 1 : 1 매칭만 가능하다.
• 공백 이후의 . 과 같은 괄호가 없는 문장도 균형 잡힌 문자열이다.
• (, [ 이 나온 후에 ), ] 가 나와야 짝이 이루어 진다. 
  • ] [ 은 짝이 아닌 경우 

풀이 과정

먼저 우리가 찾아야 할 것은 괄호들이다.

이는 StringTokenizer를 활용해 볼 예정이다. ( 물론 chatAt()을 사용하면 더 빠르다. )

다음 자료구조 스택에 대한 글과 split과 StringTokenizer비교에 관한 글을 참고하면 좋을 것 같다.

 

스택 ( 자료구조 ) - JAVA

 

[ JAVA ] 문자열 자르기 Splite VS StringTokenizer

 

 

1. 괄호 문자 저장

먼저 StringTokenizer를 통해 소괄호, 대괄호를 기준으로 문자를 나눈다.

그렇게 되면 구분자를 저장하는 StringTokenizer의 특성을 활용해 문자를 가져올 수 있다.

true로 설정하면 구분자도 Token에 포함된다.

stringTokenizer = new StringTokenizer(sentence,"([)]",true);

 

2. 괄호 문자 찾아 균형확인하기

1. 구분자에 포함된 토큰 중에 괄호를 찾는다.

2. (, [ 라면 스택에 넣는다

3 - 1. ], ) 라면 스택에서 꺼내 비교한다

3 - 2. 이 때, 동일한 모양의 괄호 즉, )일 때 ( 괄호가 나오지 않는다면 균형이 맞지 않는 문자열로 처리

while(stringTokenizer.hasMoreTokens()) {

    String token = stringTokenizer.nextToken();

    if (token.equals("(") || token.equals("[")) {
        push(token);
    }
    else if (token.equals(")")) {
        if (!pop().equals("(")) {
            isPerfect = false;
            break;
        }
    }
    else if (token.equals("]")) {
        if (!pop().equals("[")) {
            isPerfect = false;
            break;
        }
    }
}

 

 

3. 스택에 남아있는 값 확인

마지막으로 스택에 남아 있는 경우 즉, (() 와 같은 문자열이 들어온다면 ( 이 스택에 남아 균형이 맞지 않는다.

if (!delimStack.isEmpty()) isPerfect = false;

---

 

스택을 활용하여 푸는 문제로 괄호를 저장하고 저장한 값을 꺼내 올 때,
다양한 경우에 대비하여 반론이 없게 푸는 것이 중요하다.
이번 문제는 빠르게 풀 수도 있지만, charAt함수가 아닌 StringTokenizer를 사용하듯이
다양한 방법으로 풀어보는 것을 추천한다.

---

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    private static LinkedList<String> delimStack;

    private static void push(String delim){
        delimStack.addLast(delim);
    }

    private static String pop(){
        return delimStack.isEmpty() ? " " : delimStack.removeLast();
    }


    public static void main(String[] args) throws IOException {
        delimStack = new LinkedList<>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        boolean isPerfect;
        StringTokenizer stringTokenizer;

        while (true) {
            isPerfect = true;
            delimStack.clear();
            String sentence = bufferedReader.readLine();

            if(sentence.equals(".")) break;

            stringTokenizer = new StringTokenizer(sentence,"([)]",true);


            while(stringTokenizer.hasMoreTokens()) {

                String token = stringTokenizer.nextToken();

                if (token.equals("(") || token.equals("[")) {
                    push(token);
                }
                else if (token.equals(")")) {
                    if (!pop().equals("(")) {
                        isPerfect = false;
                        break;
                    }
                }
                else if (token.equals("]")) {
                    if (!pop().equals("[")) {
                        isPerfect = false;
                        break;
                    }
                }
            }

            if (!delimStack.isEmpty()) isPerfect = false;


            stringBuilder.append(isPerfect ? "yes\n" : "no\n");
        }

        System.out.println(stringBuilder);
    }
}