Correct Parentheses

올바른 괄호

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java (opens in a new tab)

내 풀이

효율성 테스트에서 시간 초과가 발생했다.

import java.util.*;
 
class Solution {
    boolean solution(String s) {
        boolean answer = false;
        String[] arr = s.split("");
        Stack<String> stack = new Stack<String>();
        int size = 0;
        for(String a : arr) {
            if(a.equals("(")) {
                stack.push(a);
                size ++;
            }
            else if(size > 0 && a.equals(")")) {
                size --;
                stack.pop();
            } else {
                size ++;
                break;
            }
        }
        if(size == 0) {
            answer = true;
        }
        return answer;
    }
}

정답 풀이

import java.util.*;
 
class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        
        char[] a = s.toCharArray();
        for(char c: a) {
            if(c == '(') {
                stack.push(c);
            }
            else {
                if(stack.isEmpty() || stack.pop() == c) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

배운점

.split() 메서드는 toCharArray에 비해서 더 큰 시간 복잡도를 가질 수 있다는 것을 배웠다.

class Solution {
    boolean solution(String s) {
        boolean answer = false;
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        int size = 0;
        for(char a : arr) {
            if(a == '(') {
                stack.push(a);
                size ++;
            }
            else if(size > 0 && a == ')') {
                size --;
                stack.pop();
            } else {
                size ++;
                break;
            }
        }
        if(size == 0) {
            answer = true;
        }
        return answer;
    }
}

실패율 두 큐의 합 같게 만들기