프로그래머스 - 올바른 괄호 문제

프로그래머스 - 올바른 괄호 문제

본 포스팅은 java로 작성되었습니다.

괄호로 이루어진 문자열이 올바른 구조인지 판단하는 문제는 자료구조 중 스택(Stack) 을 활용하면 해결할 수 있다.
이 문제의 핵심은 닫힌 괄호 )가 단순히 어떤 열린 괄호 (와 짝을 이루는 것이 아니라, 가장 최근에 등장한 열린 괄호와 정확히 짝을 이루어야 한다는 점이다.

---

1. 가장 가까운 괄호와 짝을 이루는 구조

닫힌 괄호는 왼쪽에 있는 괄호 중에서도 가장 마지막에 열린 괄호와 짝을 이루어야 한다.
이는 후입선출(Last In, First Out) 구조인 스택과 자연스럽게 연결된다.
따라서 열린 괄호가 나오면 스택에 넣고, 닫힌 괄호가 나오면 스택에서 가장 위의 열린 괄호를 꺼내서 짝을 맞추는 방식으로 접근할 수 있다.

• 조금 더 쉽게 말로 풀어보자면!!!
  '('와 ')'는 하나의 쌍이 되어야한다.
  '('가 나왔을 때 스택에 차곡 차곡 넣다가, ')'가 나오면 '('을 하나 빼면 된다.
  만약 '('와 ')'가 제대로 짝이 맞는다면 모든 문자열을 돌았을 때 스택에 남는 문자열이 없을 것이고, 오히려 다 끝났는데도 스택이 비어있지 않다면, 짝이 맞지 않는 것이다. 혹은 ')' 문자열을 만나서 스택에서 '('를 꺼내려고 했는데 이미 스택이 비어있다고해도 짝이 맞지 않다고 판단할 수 있다.

---

2. 처음 작성하며 실수한 부분

이 문제를 처음 풀면서 다음과 같은 실수를 통해 자바 문법과 자료구조 사용법을 다시 확인할 수 있었다.

• 문자열 s를 직접 for (char i : s)로 순회하려 했으나,
  자바에서 String은 문자 배열이 아니므로 s.toCharArray()로 변환해야 순회가 가능하다.

• stack.size() == 0 보다 더 직관적인 stack.isEmpty()를 사용하는 것이 가독성과 의미 전달 면에서 더 적절하다.

---

3. String과 char/Character의 차이

항목	String	char / Character
의미	여러 글자로 이루어진 문자열	하나의 문자
표현 방식	"(", "Hello"	'(', 'H'
크기	0글자 이상	항상 1글자
변환 방법	toCharArray()로 문자 배열로 변환 가능	'c'로 표현 가능

String은 한 글자라도 "("처럼 큰따옴표를 사용해야 하며, char는 작은따옴표(')를 사용한다.

---

4. 최종 코드

import java.util.Stack;

class Solution {
    public boolean solution(String s) {
        Stack<Character> stack = new Stack<>();

        // 문자열을 문자 배열로 변환하여 한 글자씩 순회
        for (char c : s.toCharArray()) {
            if (c == '(') {
                // 열린 괄호는 스택에 저장
                stack.push(c);
            } else if (c == ')') {
                // 닫힌 괄호가 나왔을 때 스택이 비어 있으면 올바르지 않은 구조
                if (stack.isEmpty()) {
                    return false;
                }
                // 가장 최근의 열린 괄호를 꺼내 짝을 맞춤
                stack.pop();
            }
        }

        if (!stack.isEmpty()) {
            return false;
        }

        return true;
    }
}