[Java] 4단계. 균형잡힌 세상 [4949번]

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

• 예제 입력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

---

• 문제 접근
  • 문자열에 포함되는 괄호는 소괄호와 대괄호 2종류
  • 문자열이 균형을 이루는 조건은 아래와 같음
    
    1. 모든 왼쪽 소괄호는 오른쪽 소괄호와만 짝을 이룸
    2. 모든 왼쪽 대괄호는 오른쪽 대괄호와만 짝을 이룸
    3. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재
    4. 모든 괄호들의 짝은 1:1 매칭만 가능
    5. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 함
  • 입력
    
    • 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호, 대괄호로 이루어져 있으며, 온점(.)으로 끝나고 길이는 100글자 이하
    • 입력의 종료 조건으로 맨 마지막에 온점 하나(".")
  • 출력
    
    • 각 줄마다 해당 문자열이 균형을 이루고 있으면 yes, 아니면 no 출력
• 문제 해결
  1. 무한 반복문으로 들어온 문자가 정확히 "."라면 반복 종료
  2. 입력받은 문자열 길이만큼 반복
  3. 정규표현식을 이용하여 소괄호와 중괄호가 아니라면 패스
  4. '(' 또는 '['일 경우 무조건 Stack에 추가
  5. ) 또는 ]일 때 Stack이 비어있으면 불균형 문자열 (항상 여는 괄호 (, [가 먼저 나오기 때문에 Stack에 있어야 함) → 반복문 종료
  6. ')'일 때 짝이 '('가 아니거나, ']'일 때 짝이 '['가 아니라면 불균형 문자열 → 반복문 종료
  7. 반복문이 종료된 후 스택이 비어있지 않더라도 불균형 문자열

 

• 정규 표현식 풀이 [메모리 : 221,672 KB / 시간 : 676 ms]

static final String REGEX = "[\\[,\\],\\(,\\)]";
public static void main(String[] args) throws IOException{
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    while(true){
        String str = br.readLine();
        if(str.equals(".")) break;

        boolean isBalanced = true;
        Stack<Character> stack = new Stack<>();

        int repeat = str.length();
        for(int i = 0; i < repeat; i++){
            char ch = str.charAt(i);
            // (, ), [, ] 이 외에는 무시
            if(!Pattern.matches(REGEX, String.valueOf(ch))) continue;
            
            if(ch == '(' || ch == '[') {
                stack.push(ch);
            } else { // )이거나 ]일 때 실행
                if(stack.isEmpty()) { // 비어있으면 no
                    isBalanced = false;
                    break;
                }
                char pop = stack.pop();
                if((ch == ')' && pop != '(') || (ch == ']' && pop != '[')){
                    // ')'일 때 짝(pop)이 '('가 아니라 '['라면 불균형
                    // ']'일 때 짝(pop)이 '['가 아니라 '(' 라면 불균형
                    isBalanced = false;
                    break;
                }
            }
        }
        if(!stack.isEmpty()) isBalanced = false;
        sb.append(isBalanced ? "yes" : "no").append("\n");
    }
    System.out.println(sb);
}

• 정규 표현식 없이 단순 if문 풀이 [메모리 : 19,102 KB / 시간 : 184 ms]

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

    while(true){
        String str = br.readLine();
        if(str.equals(".")) break;

        boolean isBalanced = true;
        Stack<Character> stack = new Stack<>();

        int repeat = str.length();
        for(int i = 0; i < repeat; i++){
            char ch = str.charAt(i);
            // (, ), [, ] 이 외에는 무시
            if(ch == '(' || ch == '[') {
                stack.push(ch);
            } else if(ch == ')' || ch == ']'){ // )이거나 ]일 때 실행
                if(stack.isEmpty()) { // 비어있으면 no
                    isBalanced = false;
                    break;
                }
                char pop = stack.pop();
                if((ch == ')' && pop != '(') || (ch == ']' && pop != '[')){
                    // ')'일 때 짝(pop)이 '('가 아니라 '['라면 불균형
                    // ']'일 때 짝(pop)이 '['가 아니라 '(' 라면 불균형
                    isBalanced = false;
                    break;
                }
            }
        }
        if(!stack.isEmpty()) isBalanced = false;
        sb.append(isBalanced ? "yes" : "no").append("\n");
    }
    System.out.println(sb);
}

---

• str.charAt(i)를 했을 때 소괄호 & 대괄호가 아닐 경우 continue로 스킵해버리는 것이 더 효율적이라 생각되어 정규 표현식을 사용하여 소괄호, 대괄호일 때만 로직이 실행되도록 코딩
• 하지만, 나의 생각과 달리 정규표현식을 쓴 것이 단순 if문을 쓴 것에 비해 시간 & 공간 복잡도가 심각하게 안 좋은 수준이였음
• ChatGPT에 의하면, Pattern.matches(REGEX, String.valueOf(ch)) 코드에서 ch를 String으로 변환을 한 후 정규표현식 검사를 하는데, 여기서 추가적인 메모리 할당과 컴파일 과정이 필요하여 성능에 영향을 끼친다고 함
• 특히, 반복문 내부에서 실행되는 문자열이 길어지면 길어질수록 모든 문자 하나하나를 char → String으로 바꾸는 오버헤드가 훨씬 더 커지기 때문인 것으로 추측 됨
• 즉, 정규표현식으로 풀이한 방식은 패턴 매칭과 컴파일이 포함되기 때문에 느리다고 함