BOJ_Stack_4949_균형잡힌 세상 (Java)

문제 풀이에 대한 오류 지적 및 개선 방향 제시는 항상 환영합니다.
알고리즘 문제를 엄청 잘 풀고 막 문제 보자마자 아 이거네 쉽네 ㅎㅎ 이렇게 푸는 입장이 아니라서
그 어떤 문제에 대한 비판 지적 방향 제시는 언제나 감사하게 받겠습니다. 

이 문제가 올라가는 저장소 : https://github.com/hwk0911/Algoritm_Step_By_Step

hwk0911/Algoritm_Step_By_Step

 

4949번 - 균형 잡힌 세상 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	8322	2746	2308	33.605%

문제

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

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

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

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

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

입력

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

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

출력

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

제한

 

예제 입력 1

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

예제 출력 1

yes
yes
no
no
no
yes
yes

힌트

7번째의 "."와 같이 괄호가 하나도 없는 경우도 균형 잡힌 문자열로 간주할 수 있다.

 

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

public class BOJ_Stack_4949 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String words = "";

        while (!(words += br.readLine()).equals(".")) {
            if (words.charAt(words.length() - 1) == '.') {
                words = changeWord(words);
                System.out.println(checkBalance(words));

                words = "";
            }
        }
    }

    public static String changeWord(String words) {
        String subWords = "";

        for (int index = 0, size = words.length(); index < size; ++index) {
            switch (words.charAt(index)) {
                case '(':
                case ')':
                case '[':
                case ']':
                    subWords += words.charAt(index);
            }
        }

        return subWords;
    }

    public static String checkBalance(String words) {
        ArrayList<Character> check = new ArrayList<>();

        for (int index = 0, size = words.length(); index < size; ++index) {
            if(words.charAt(index) == ')'){
                if(check.isEmpty() || check.get(check.size() - 1) != '('){
                    return "no";
                }
                else{
                    check.remove(check.size() - 1);
                }
            }
            else if(words.charAt(index) == ']'){
                if(check.isEmpty() || check.get(check.size() - 1) != '['){
                    return "no";
                }
                else{
                    check.remove(check.size() - 1);
                }
            }
            else{
                check.add(words.charAt(index));
            }
        }

        if(check.isEmpty()){
            words = "yes";
        }
        else{
            words = "no";
        }

        return words;
    }
}

1. main함수
   1. words에 새로운 입력을 계속 더해 연산의 대상이 될 String을 생성한다.
2. changeWord함수
   
   1. 변환한 결과를 저장할 subWords를 선언한다.
   2. 문제의 연산에 필요한 괄호들만 subWords에 저장하여 반환한다.
3. checkBalance
   1. 스트링을 전체 검사한다.
   2. ) or ]이 들어온 경우
      1. 스택으로 사용할 ArrayList가 비어있거나, ArrayList의 마지막 원소가 대응하는
         괄호가 아닌 경우 "no"를 반환한다.
      2. 위의 경우가 아닐 때, ArrayList의 마지막 원소를 제거한다.
   3. 2번의 경우가 아닐 때, ArrayList에 add()를 통해 마지막 원소로 저장한다.
   4. 2 ~ 3번 반복
   5. 마지막 예외처리. ArrayList.isEmpty()의 결과가 true일 경우
      1. true : words = "yes";
      2. false : words = "no"
   6. words를 리턴하여 출력한다.

괄호 문제는 대표적인 스택 문제다. 코딩 테스트에도 자주 나온다.

주의할 점은 항상 그렇듯 예외처리를 주의해야 한다.

1. "((((((((((((((." 또는 "[[[[[[[[[[[."가 들어오는 경우
2. ")(."가 들어오는 경우
3. "([)]"가 들어오는 경우