[Java] 프로그래머스 - 올바른 괄호

닫는 괄호가 먼저 나오지 않는지 순회 중간에도 확인해야 하는 문제

 

1. 문제 유형

스택(Stack), 문자열, 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 여는 괄호 (는 더하고 닫는 괄호 )는 빼서 마지막 결과만 0이면 올바른 괄호라고 생각했다.

오답 원인: 최종 개수보다 중간 순서가 올바른지를 먼저 봐야 했다. 예를 들어 )( 는 최종 합만 보면 0이지만 닫는 괄호가 먼저 나왔으므로 올바른 괄호가 아니다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 짝이 없는 닫는 괄호가 먼저 나오거나, 순회를 마쳤는데도 여는 괄호가 남아있으면 실패

풀이 아이디어(Stack 사용):

1. ( 이면 Stack에 push 한다.
2. ) 이면 Stack에서 pop 한다. 단, 스택이 비어있다면 즉시 false 반환
3. 문자열 끝까지 순회한 후 Stack이 완전히 비어있으면 true, 남아있으면 false를 반환한다.

4. 구현 코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                stack.push('(');
            } else if (s.charAt(i) == ')') {
                if(stack.isEmpty()) {
                    return false;
                } else {
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }
}

시간 복잡도: O(N) / 공간 복잡도: O(N)

---

 

인사이트

• 괄호 종류가 하나뿐이면 count로도 풀 수 있다.

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/12909