프로그래머스 알고리즘 고득점 Kit - [Lv.2] 올바른 괄호 (Java)

문제 출처 - 링크

알고리즘 분류

• 스택/큐

📋 문제 요약 설명

• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
• 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다.
• 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하시오.

💡 알고리즘 설계 / 접근 방법

1. 스택에 '(' 이면 값을 넣고, ')' 이면 값을 꺼낸다.
2. 스택에서 값을 꺼낼 때 스택이 비어있으면 괄호가 올바르지 않은 것이다.

✅ 풀이

시간 복잡도 → O(N)

1. s.toCharArray() : O(N)
   1. N = s.length()
2. for 루프 : O(N)
3. 내부 stack 연산 여러번 : O(1) * N = O(N)

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<Integer> stack = new Stack<>();
        
        for(char ch : s.toCharArray()) {
            if(ch == '(')
                stack.push(1);
            else if(ch == ')' && !stack.isEmpty())
                stack.pop();
            else
                return false;
        }
        
        return stack.isEmpty();
    }
}