[오늘의 문제] 올바른 괄호

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

문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
입출력 예
s answer
"()()" true
"(())()" true
")()(" false
"(()(" false
입출력 예 설명
입출력 예 #1,2,3,4
문제의 예시와 같습니다.

내가 작성한 코드문

import java.util.*;
class Solution {
    boolean solution(String s) {
        boolean answer = true;

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        
        Stack<Character> stack = new Stack<>();
        // 반복문 돌며 스택에 추가
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            
            // 여는 괄호는 push
            if(ch == '('){
                stack.push(s.charAt(i));
            } else {
                // 닫는 괄호인데 스택이 비어있으면 짝이 안 맞음
                if (stack.isEmpty()) return false;
                stack.pop();
                // 짝이 맞는 여는 괄호 제거
            }
            
            // 닫는 괄호인데 스택이 비어있으면 짝이 안 맞음
        }
        System.out.println(answer);
        return stack.isEmpty();
    }
}

스택의 기본문제다. 잘 보면서 공부하길

다른 사람의 풀이

class Solution {
    boolean solution(String s) {
        boolean answer = false;
        int count = 0;
        for(int i = 0; i<s.length();i++){
            if(s.charAt(i) == '('){
                count++;
            }
            if(s.charAt(i) == ')'){
                count--;
            }
            if(count < 0){
                break;
            }
        }
        if(count == 0){
            answer = true;
        }

        return answer;
    }
}

핵심 아이디어:
count++ : 여는 괄호는 증가

count-- : 닫는 괄호는 감소

count < 0 : 닫는 괄호가 먼저 나오면 → 짝이 안 맞음 → false

반복 끝나고 count == 0이면 괄호 짝이 맞음 → true

✅ 이 방법이 좋은 이유
스택 사용보다 더 빠르고 메모리도 적게 사용함 (O(1) 공간)

실제 괄호 짝을 기억하지 않고도 균형 여부만 체크하면 되기 때문

✅ 스택 vs 카운터 비교
| 구분 | 스택 풀이 | 카운터 풀이 |
| --- | ---------------- | -------------------- |
| 직관성 | 괄호 짝을 직접 추적 | 균형만 추적 |
| 성능 | O(N) 시간, O(N) 공간 | O(N) 시간, O(1) 공간 |
| 가독성 | 괄호가 많을 땐 더 직관적 | 짧고 빠름 |

import java.util.Stack;
class Solution {
    boolean solution(String s) {
        boolean answer = true;  
        String res = "YES";
        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    st.push(1);
                } else if (s.charAt(i) == ')') {
                    if (st.isEmpty()) {
                        answer = false;
                        break;
                    } else {
                        st.pop();
                    }
                }
            }

            if(!st.isEmpty()) {

                answer = false;

            }

            System.out.println(res);
return answer;
    }   

}

유사하다.

이 부분은 괄호의 짝을 맞추기 위해 스택을 사용하는 전형적인 방식이다. 괄호가 열릴 때 push, 닫힐 때 pop.
닫는 괄호가 먼저 나올 경우 (isEmpty()), 짝이 맞지 않으므로 false.

✅ 전체 코드 리뷰
👍 장점:
기능적으로 정확합니다. 정상적으로 작동해서 "()", "(())" → true, ")(", "(()" → false 판단 가능.

스택을 이용한 직관적인 로직