[알고리즘] 프로그래머스 - 올바른 괄호 (Stack)

1. 문제

2. 나의 풀이

전형적인 Stack 문제로 반복문을 통해서 문자열을 순회한다. 문자가 '(' 일 경우에는 Stack에 넣어주고 ')'일 경우에는 Stack에서 제거한다. 만약 더이상 제거할게 없는데 ')' 문자가 오면 올바른 괄호가 아니다.

 

또한 문자열을 모두 순회하고나서 Stack에 '('가 남아있다면 괄호가 제대로 닫히지 않고 끝났기 때문에 올바른 괄호가 아니다. 

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        Stack stack = new Stack<String>();
        int len = s.length();
        for(int i=0;i<len;i++) {
            if('(' == s.charAt(i)) {
                stack.push(String.valueOf(s.charAt(i)));
            } else if(')' == s.charAt(i) && !stack.empty()) {
                stack.pop();
            } else if(')' == s.charAt(i) && stack.empty()) {
                answer = false;
                break;
            }
        }
        
        if(!stack.empty()) {
            answer = false;
        }

        return answer;
    }
}

시간 복잡도 : O(n) 

공간 복잡도 : O(n)

 

현재 공간 복잡도는 Stack에 문자열을 넣기 때문에 O(n)으로 계산된다. 개선사항으로 공간 복잡도를 줄일 수 있다.

 

3. 공간 복잡도 개선

Stack 대신에 sum이라는 변수를 사용하면 공간 복잡도를 O(1)로 줄일 수 있다.

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        int sum = 0;
        int len = s.length();
        for(int i=0;i<len;i++) {
            if('(' == s.charAt(i)) {
                sum += 1;
            } else if(')' == s.charAt(i) && sum > 0) {
                sum -= 1;
            } else if(')' == s.charAt(i) && sum <= 0) {
                answer = false;
                break;
            }
        }
        
        if(sum != 0) {
            answer = false;
        } 

        return answer;
    }
}