[Java] 스택(stack) 설명과 스터디 과제1. 괄호 짝맞추기

1. 스택(Stack)이란?

 - 스택은 LIFO (Last In First Out) 구조를 가진 자료구조이다. (프링글스..)

- 마지막에 추가된 데이터가 가장 먼저 제거된다.

   예시: 접시를 쌓는 것과 비슷하다. 새 접시를 올리면 맨 위에 놓이고, 접시를 꺼낼 때도 맨 위에서부터 꺼낸다.

 

2. 스택의 주요 연산

1. push():

  - 데이터를 스택의 맨 위에 추가한다.

    예: stack.push(1) → 스택에 1 추가.

2. pop():

  - 스택의 맨 위에 있는 데이터를 제거하고 반환한다.

  -  스택이 비어 있을 경우, EmptyStackException을 발생시킨다.

3. peek():

  - 스택의 맨 위에 있는 데이터를 제거하지 않고 반환한다.

  - 스택이 비어 있으면 예외를 발생시킨다.

4. isEmpty():

  -  스택이 비어 있는지 확인한다.

  -  비어 있으면 true, 비어 있지 않으면 false를 반환한다.

5. size():

  - 스택에 저장된 데이터의 개수를 반환한다.

6. contains(Object o):

-  특정 값이 스택에 포함되어 있는지 확인한다.

-  포함되어 있으면 true, 없으면 false를 반환한다.

import java.util.Stack;

public class StackFundamental {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 1. 요소 추가
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 2. 스택 상태 확인
        System.out.println(stack);  // [1, 2, 3]

        // 3. 맨 위 요소 확인
        System.out.println("제일 꼭대기의 값 : " + stack.peek());  // 3

        // 4. 요소 제거
        System.out.println("꺼낸 값 : " + stack.pop());  // 3

        // 5. 스택이 비어있는지 확인
        System.out.println("스택이 비었는가? " + stack.isEmpty());  // false

        // 6. 스택 크기 확인
        System.out.println("스택에 저장 된 원소 수 : " + stack.size());  // 2

        // 7. 특정 요소 포함 여부 확인
        System.out.println("스택에 1 이 있는가? " + stack.contains(1));  // true
    }
}

 

3.스택의 동작 이해

  3.1 요소 추가는 항상 스택의 맨 위에 이루어진다.

  3.2. 요소 제거는 항상 스택의 맨 위에서 이루어진다.

  3.3 스택 상태:

     • 처음: [1, 2, 3].

     •pop() 이후: [1, 2].

 

4. 스택의 활용 예

• 괄호 검사: 열고 닫는 괄호의 짝이 맞는지 확인할 때 사용.

• DFS (깊이 우선 탐색): 그래프 탐색에서 호출 순서를 관리할 때 사용.

• Undo 기능 구현: 작업 기록을 저장하여 이전 상태로 복구할 때 사용.

 

스택은 데이터를 일시적으로 저장하거나, 순서를 관리하는 문제에서 자주 사용되는 기본 자료구조이다.

---

과제 1. 완벽한 괄호

• Stack 을 활용하여 괄호의 열고 닫힘이 완벽한 괄호인 경우 true, 아닌 경우 false 를 반환하는 solution 코드를 완성하세요

 

---

1. 문제 분석

   1.1 목표 : 주어진 문자열이 “완벽한 괄호”인지 확인하는 함수 solution을 작성한다.

   1.2 조건 : 

• 열린 괄호 (는 닫힌 괄호 )와 정확히 짝을 이루어야 한다.

• 모든 닫힌 괄호는 스택에 열린 괄호가 있을 때만 짝을 이룰 수 있다.

• 문자열을 모두 확인했을 때 스택이 비어 있어야 완벽한 괄호이다.

 

2. 해결 방안

괄호의 열림과 닫힘의 순서를 유지하기 위해 LIFO구조가 필요한데 이를 위해 스택을 사용한다.

열린 괄호(는 스택에 넣고, 닫힌 괄호를 만났을 때 스택에서 하나를 꺼내서 매칭한다. 

 

3. 알고리즘.

1) 문자열 s를 순회하면서 각 문자 c를 확인한다.

2) 열린 괄호인 경우에는, 스택에 넣는다.

3) 닫힌 괄호인 경우에는, 스택이 비어 있다면 닫힌 괄호와 매칭될 열린 괄호가 없으므로 false를 반환한다.

    스택이 비어있지 않다면 스택에서 열린 괄호를 하나를 꺼낸다.

4) 문자열 순회가 끝난 후: 

     스택이 비어 있다면 완벽한 괄호이다. - true 반환

     스택이 비어 있지 않다면 완벽하지 않다. - false 반환

 

4. 문제 분석

 4.1 열린 괄호와 닫힌 괄호의 짝을 확인 :

- 열린 괄호를 만날 때마다 스택에 저장한다.

- 닫힌 괄호를 만날 때마다 스택에서 열린 괄호 하나를 제거(pop)한다.

이렇게 하면 닫힌 괄호는 가장 최근에 추가된 열린 괄호와 매칭된다. 

 4.2 닫힌 괄호가 스택이 비었을 때 발생 :

- 닫힌 괄호가 왔을 때 스택이 비어 있으면 매칭될 열린 괄호가 없다는 뜻이다.

이런 경우 즉시 false 반환.

 4.3 문자열을 모두 확인 후 스택 상태 확인 :

- 모든 열린 괄호가 매칭되었다면 스택은 비어 있어야 한다. 

- 스택이 비어 있지 않다면 매칭되지 않은 열린 괄호가 남아 있다는 뜻으로 false를 반환한다. 

import java.util.Stack;

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

				// 의사(Pseudo) 코드
        // 1. 열린 괄호 ”(“ 를 만나면? 스택에 넣는다 (push)
        // 2. 닫힌 괄호를 ”)” 만나면? 스택에 있는 애를 뽑는다 (pop)
        // 3. 문자열이 끝났어요
        //    스택이 비었으면? -> 완벽한 괄호 -> True
        //    스택이 안비었으면? -> False
        // 4. 문자열이 안끝났어요
        //    스택이 비었으면? -> False
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
            // 열린 괄호는 스택에 추가
            stack.push(c);
        }  else if (c == ')') {
             // 닫힌 괄호를 만났을 때
             if (stack.isEmpty()) {
                 // 매칭될 열린 괄호가 없으면 false
                 return false;
             }
             stack.pop(); // 매칭되는 열린 괄호 제거
        }
      }
       // 모든 문자열 순회후 스택이 비어 있으면 true, 아니면 false
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String tc1 = "()()"; // true
        String tc2 = "()()("; // false
        String tc3 = "())"; // false
        String tc4 = "((((((()))()()))))()()())(())))"; // false

        System.out.println(solution(tc1));
        System.out.println(solution(tc2));
        System.out.println(solution(tc3));
        System.out.println(solution(tc4));
    }
}