[Java] BOJ 4949 균형잡힌 세상

문제 

문제 링크 https://www.acmicpc.net/problem/4949

• 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
  • 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
  • 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
  • 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
  • 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
  • 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
• 정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
• 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
• 입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.
• 각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

 

아이디어

• stack을 써서 여는 작은 괄호가 들어올 때마다 "s"를 넣고 여는 큰 괄호가 들어올 때마다 "b"를 넣었다.
• 닫는 작은 괄호가 들어왔을 때, 마지막에 들어온게 "s"라면 stack에서 맨 위에 문자를 삭제하고 반복문을 계속하지만, 만약 맨 위에 있는 문자가 "s"가 아니라면 반복문을 종료한다.
• 마찬가지로 닫는 큰 괄호가 들어왔을 때, 마지막에 들어온게 "b"라면  stack에서 맨 위에 문자를 삭제하고 반복문을 계속하지만, 만약 맨 위에 있는 문자가 "b"가 아니라면 반복문을 종료한다.
• 그리고 어떤 닫는 괄호든 닫는 괄호가 들어왔는데 stack이 비어있다면 닫는 괄호가 여는 괄호보다 먼저 들어와서 순서가 잘못됐다는 뜻이므로 반복문을 종료한다.
• 반복문이 마지막까지 다 돈 후, 만약 stack이 비어있다면 문장의 균형이 맞다는 뜻이므로  "yes"를 출력하고 stack이 비어있지 않다면 문장의 균형이 맞지 않다는 뜻이므로 "no"를 출력한다. 

겪은 시행착오

• 처음에 메모리 초과가 계속 나서 뭐가 문제인가 했다... 알고보니 문장을 입력받고 문자에 접근할 때, 's.split("")[i]' 이런식으로 접근했는데 이 부분에서 메모리 초과가 나는 것이였다...
• 그래서 저 부분을 's.charAt[i]'로 바꿔주니 메모리 초과가 나지 않았다... ㅜㅜ 앞으로도 split()으로 문자를 접근하기 보단 charAt[]으로 접근해야겠다... 

메모리 초과의 이유를 찾지 못했었다.... ㅜㅜ

메모리 초과를 조심하자...!

코드

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

public class BOJ4949 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        while(true){
            // 입력되는 한 문장
            String s = br.readLine();

            // 문장의 길이
            int s_len = s.length();

            Stack<String> smb = new Stack<>();

            // 만약 문장의 시작이 길이와 같아졌을 때
            if(s_len == 1){
                // 만약 그 문장이 '.' 하나라면
                if(s.equals(".")){
                    // 종료
                    break;
                }
            }

            for(int i = 0; i < s_len; i++){
                //만약 소괄호 여는게 하나 있다면 스택테 s를 넣음
                if(s.charAt(i) == '('){
                    smb.add("s");
                }
                // 만약 소괄호 닫는게 하나 있다면 카운트에서 - 1
                else if(s.charAt(i) == ')'){
                    // 만약 스택이 비어있지 않다면
                    if(!smb.empty()){
                        String stk = smb.peek();

                        // 만약 최근에 들어온게 소괄호라면 닫는 순서가 맞으므로 pop
                        if(stk.equals("s")){
                            smb.pop();
                        }
                        else{
                            sb.append("no" + "\n");
                            break;
                        }
                    }
                    // 만약 비어있다면 여는게 없는데 닫는게 들어온 것이므로 반복문 종료
                    else{
                        sb.append("no" + "\n");
                        break;
                    }
                }
                // 만약 대괄호 여는게 하나 있다면 스택테 b를 넣음
                else if(s.charAt(i) == '['){
                    smb.add("b");
                }
                // 만약 대괄효 닫는게 하나 있다면
                else if(s.charAt(i) == ']'){
                    // 만약 스택이 비어있지 않다면
                    if(!smb.empty()){
                        String stk = smb.peek();

                        // 만약 최근에 들어온게 대괄호라면 닫는 순서가 맞으므로 pop으로 뺌
                        if(stk.equals("b")){
                            smb.pop();
                        }
                        // 아니라면 "no"출력
                        else{
                            sb.append("no" + "\n");
                            break;
                        }
                    }
                    // 만약 비어있다면 여는게 없는데 닫는게 들어온 것이므로 반복문 종료
                    else{
                        sb.append("no" + "\n");
                        break;
                    }
                }

                // 반복문의 마지막이 된다면
                if(i == (s_len - 1)){
                    if(smb.empty()){
                        sb.append("yes" + "\n");
                    }
                    // 만약 반복문이 끝나고 소괄호와 대괄호의 카운트가 0이 아니라면
                    // 남는게 있거나 순서가 잘못됐다는 뜻이므로 "no" 출력
                    else{
                        sb.append("no" + "\n");
                    }
                }

            }
        }

        System.out.println(sb);
    }
}