4949 균형잡힌 세상 JAVA

이번 문제도 어렵지 않았지만, 문자열을 다루는데 공부가 된거 같았다.

 

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

 

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

public class S4949 {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = null;

        loop1:
        while(true) {
            String input = br.readLine();
            if(input.equals(".")) break; // .만을 입력받으면 break;
            stack = new Stack<>();
            char small = '(', big = '[';

            for(char tmp : input.toCharArray()) { // input을 문자 배열로 변환
                if(tmp == small) // (일 때 stack에 (를 저장
                    stack.push(small);
                else if(tmp == big) // [일 때 stack에 [를 저장
                    stack.push(big);

                if(tmp == ')') { // )라면 비어있는지와 직전 스택이 (인지 체크
                    if(!checkExp(small,stack)) // 해당 메서드에서 false가 나왔다먄
                        continue loop1;        // 반복문을 건너뛴다.
                }
                else if(tmp == ']') {// ]라면 비어있는지와 직전 스택이 [인지 체크
                    if (!checkExp(big,stack)) // 해당 메서드에서 false가 나왔다면
                        continue loop1;     // 반복문을 건너뛴다.
                }
            }

            if(stack.empty()) // 최종적으로 스택이 비어있다면 yes
                sb.append("yes\n");
            else // 마지막으로 ([ 에 대한 처리를 해준다.
                sb.append("no\n");
        }
        System.out.println(sb);
    }

    public static boolean checkExp(char ch,Stack<Character> stack) {
        if(stack.empty() || stack.peek() != ch) { // stack이 비어있는데 꺼내려고 했거나,
            sb.append("no\n");                  // (] [) 과 같은 경우에 no를 저장하고 리턴한다.
            return false;
        }
        stack.pop(); // 여기까지 코드가 진행됐다면 문제 없기 때문에 pop을 하여 업데이트
        return true;
    }
}

 

이 문제는 어려운 문제가 아니다. 하지만 이 문제를 통해서 발생할 수 있는 모든 경우의 수를 고려해야 한다는 걸 다시금 느꼈다.

 

이 문제에서 출력예시와 동일한데  틀렸다고 나온다면 ([ 에 대한 처리를 올바르게 하였는지 체크하는게 좋을 것 같다.

 

그리고 마지막으로 정규식을 이용해서 한번 제출 해봤다.

 

별건 아니고, 괄호를 제외한 문자들은 괄호체크에 영향이 없으므로 괄호만 반복문을 통하여 체크해보고 싶었다.

String exp = String.join("",input.split("[0-9a-zA-Z]"))
        .replaceAll("\\s","");

 

 

단순히 input 다음 라인에 위와 같이 변경해주면 된다. 이렇게 하면 dsfkaf(dfjsk)dfs((afs)] 도 "()(()]"로 짤라내어 검사를 할 수 있다. 

이것도 물론 맞는 방식이긴 하나 아래 사진과 같이 시간이 2배 이상 더 걸렸다.

 

520ms는 정규식 사용, 208ms는 아무것도 안한 첫번째 코드이다

 

정규식이라고 해서 마법은 아니였다. 시간 복잡도가 오히려 증가 됐는데 그 이유는 소스코드를 보고 이해를 했다.

괄호만 추출해서, 괄호를 검사하면 while문에서 괄호 이외의 문자를 검사 안해도 된다는 장점이 있겠지만, 

현재 상황에선 괄호를 추출하고, 공백을 제거하는 것이 내부적으로 반복문으로 구성되어 있기에 시간 복잡도가 오히려 더 증가한 것이다.

그러니까 결론은 배보다 배꼽이 더 커져버렸다 

 

좀 신기했던 건, 난이도가 실버4는 저평가 된거 같았다 ..