[프로그래머스] 스택/큐_올바른 괄호

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

프로그래머스

 

---

 

 

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

제한사항

문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

풀이

import java.util.Stack;

class Solution {
    public boolean solution(String s) {
        // 스택 생성: 괄호의 짝을 맞추기 위한 용도
        Stack<Character> stack = new Stack<>();
        
        // 문자열의 각 문자를 순회합니다.
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 만약 '('라면 스택에 push
            if (c == '(') {
                stack.push(c);
            } else { // c == ')'
                // 만약 스택이 비어있다면, ')'가 먼저 나온 경우이므로 false 반환
                if (stack.isEmpty()) {
                    return false;
                }
                // 그렇지 않다면, 스택의 가장 위의 '('를 pop
                stack.pop();
            }
        }
        
        // 모든 문자를 확인한 후, 스택이 비어있으면 올바른 괄호, 아니면 false 반환
        return stack.isEmpty();
    }
}

 

---

1. 문제 개요

문제 설명:

• 주어진 문자열 s는 오직 '('와 ')' 문자만으로 이루어져 있습니다.
• 올바른 괄호 문자열이란, 모든 '('에 대해 반드시 이후에 ')'가 짝지어져서 열고 닫히는 순서가 올바른 경우를 말합니다.
  • 예: "()()", "(())()"는 올바른 괄호 문자열입니다.
  • 예: ")(()","(()(" 등은 올바르지 않습니다.
• 목표는 문자열 s가 올바른 괄호 문자열인지 판단하여, 올바르면 true, 아니면 false를 return 하는 것입니다.

문제 제한사항:

• 문자열 s의 길이는 100,000 이하입니다.

---

2. 알아야 할 기본 개념

2.1. 괄호(Parentheses)와 균형(Balanced)

• 괄호의 쌍:
  • '('는 여는 괄호, ')'는 닫는 괄호입니다.
  • 올바른 괄호 문자열에서는 모든 여는 괄호에 대해 반드시 나중에 대응하는 닫는 괄호가 있어야 합니다.
• 균형 잡힌 괄호:
  • 문자열을 왼쪽부터 순서대로 읽었을 때, 닫는 괄호가 나타나기 전에 항상 여는 괄호의 수가 많아야 합니다.
  • 최종적으로 모든 괄호가 짝지어졌다면 균형이 잡혔다고 판단할 수 있습니다.

2.2. 스택 (Stack) 자료구조

• 정의:
  스택은 후입선출(LIFO, Last-In-First-Out) 방식으로 데이터를 저장하는 자료구조입니다.
  (가장 마지막에 넣은 것을 먼저 뺀다)

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.pop(); // 2 제거

• 기본 연산:
  • push: 스택의 맨 위에 데이터를 추가합니다.
  • pop: 스택의 맨 위 데이터를 제거하고 반환합니다.
  • isEmpty: 스택이 비어 있는지 확인합니다.
• 왜 스택을 사용하는가?
  • 괄호 문제에서, 여는 괄호 '('를 만나면 나중에 짝이 되는 닫는 괄호 ')'와 매칭시켜야 합니다.
  • 스택을 사용하면 가장 최근에 추가한 '('와 짝지어 쉽게 pop할 수 있어, 올바른 괄호의 순서를 효과적으로 관리할 수 있습니다.

---

3. 문제 해결 아이디어

1. 문자열을 순회하면서 스택을 활용
   • 문자열의 각 문자를 왼쪽부터 차례로 읽어갑니다.
2. 여는 괄호 처리:
   • 만약 현재 문자가 '('이면, 스택에 push합니다.
3. 닫는 괄호 처리:
   • 만약 현재 문자가 ')'이면,
     • 스택이 비어있다면 : 닫는 괄호가 먼저 나온 경우이므로 올바르지 않습니다.
       → 즉시 false 반환
     • 스택이 비어있지 않다면 : 스택에서 가장 최근의 '('를 pop합니다.
4. 최종 검사:
   • 문자열 전체를 읽은 후, 스택이 비어있다면 모든 여는 괄호에 대응하는 닫는 괄호가 있었다는 의미이므로 올바른 괄호 문자열입니다.
   • 만약 스택에 남아있다면, 여전히 매칭되지 않은 여는 괄호가 있으므로 올바르지 않습니다.

---

4. 자바 코드 예제 (스택 활용)

import java.util.Stack;

class Solution {
    public boolean solution(String s) {
        // 1. 스택 생성: 괄호의 짝을 맞추기 위한 용도
        Stack<Character> stack = new Stack<>();
        
        // 2. 문자열의 각 문자를 순회합니다.
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 2-1. 만약 '('라면 스택에 push
            if (c == '(') {
                stack.push(c);
            } else { // 2-2. 만약 ')'라면
                // 스택이 비어있다면, 닫는 괄호가 먼저 나온 경우이므로 false 반환
                if (stack.isEmpty()) {
                    return false;
                }
                // 그렇지 않다면, 스택의 가장 위의 '('를 pop하여 짝을 맞춘다.
                stack.pop();
            }
        }
        
        // 3. 모든 문자를 확인한 후, 스택이 비어있으면 올바른 괄호, 아니면 false 반환
        return stack.isEmpty();
    }
}

---

5. 코드 해설

5.1. 스택 생성

• Stack<Character> stack = new Stack<>();
  → 괄호의 짝을 맞추기 위해 '('를 만날 때마다 스택에 저장합니다.

5.2. 문자열 순회

• for (int i = 0; i < s.length(); i++)
  → 문자열 s의 각 문자를 왼쪽부터 오른쪽으로 하나씩 확인합니다.
• 여는 괄호 '(' 처리:
  • if (c == '(') 조건이 참이면, 현재 문자를 스택에 추가합니다.
    → 스택에 추가된 순서는 나중에 닫는 괄호 ')'와 짝지어집니다.
• 닫는 괄호 ')' 처리:
  • else 부분에서, 현재 문자가 ')'인 경우를 처리합니다.
  • 먼저, if (stack.isEmpty())를 통해 스택이 비어있는지 확인합니다.
    → 스택이 비어있으면 짝이 맞는 여는 괄호가 없으므로 바로 false를 반환합니다.
  • 그렇지 않으면, stack.pop()을 호출하여 스택에서 마지막에 추가된 '('를 제거하고 짝을 맞춥니다.

5.3. 최종 검사

• 반복문 종료 후, return stack.isEmpty();
  → 모든 문자를 확인한 후 스택이 비어있다면, 모든 여는 괄호가 닫는 괄호와 제대로 짝지어졌다는 뜻입니다.
  • 만약 스택에 남아 있다면, 여전히 짝지어지지 않은 '('가 존재하므로 올바른 괄호 문자열이 아닙니다.

---

6. 결론 및 요약

• 핵심 개념:
  • 괄호의 균형: 여는 괄호와 닫는 괄호가 올바른 순서로 짝지어져야 함.
  • 스택의 LIFO 특성: 가장 최근에 들어온 '('가 닫는 괄호와 짝지어지므로, 스택이 적합한 자료구조입니다.
• 문제 해결 과정:
  1. 문자열을 순회하면서 '('는 스택에 추가하고, ')'는 스택에서 제거합니다.
  2. 중간에 ')'를 만났는데 스택이 비어있다면 즉시 false를 반환합니다.
  3. 모든 문자를 확인한 후 스택이 비어있으면 올바른 괄호 문자열(true), 그렇지 않으면 false입니다.