# Stack

## 개념

먼저 들어간 것이 마지막에 나오는 선입후출(FILO, First In Last Out) 방식

## 문제 1. 괄호 회전하기

### 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의한다.

* `()` , `[]` , `{}` 는 모두 올바른 괄호 문자열이다.
* 만약 A가 올바른 괄호 문자열이라면, `(A)`, `[A]`, `{A}` 도 올바른 괄호 문자열이다.
* 만약 A, B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열이다.
  * A = `{}` , B = `([])` 
  * `{}([])` 도 올바른 괄호 문자열
* 대괄호, 중괄호 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어진다.
* s를 왼쪽으로 x (0 <= x < s의 길이) 칸 만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 반환하는 solution() 함수를 완성해라.

### 제약 조건

* s의 길이는 1 이상 1,000 이하

### 입출력의 예

| s        | result |
| -------- | ------ |
| `[](){}` | 3      |
| `}]()[{` | 2      |

### 코드

```kotlin
import java.util.Stack

class Solution {
    fun isValid(s: String): Boolean {
        val stack = Stack<Char>()

        for (char in s) {
            // 2.1. 현재 문자를 확인
            when (char) {
                '(', '{', '[' -> stack.push(char)
                ')', '}', ']' -> {
                    // 스택에서 하나를 peek 함
                    if (stack.isEmpty()) return false
                    val top = stack.peek()
                    // 2.2. 현재 괄호와 peek한 괄호가 올바른 괄호가 동일한지 확인
                    if ((char == ')' && top == '(') ||
                        (char == '}' && top == '{') ||
                        (char == ']' && top == '[')) {
                        // 2.2.1. 동일할 경우 pop 한 후 횟수 증가
                        stack.pop()
                    } else {
                        // 2.2.2. 동일하지 않을 경우 false 반환
                        return false
                    }
                }
            }
        }
        return stack.isEmpty()
    }
    
    fun solution(s: String): Int {
        var count = 0
        val length = s.length

        for (i in 0 until length) {
            // 1. 문자열을 왼쪽으로 이동시킴
            val rotated = s.substring(i) + s.substring(0, i)

            // 2. 문자열을 순회하여 올바른 괄호인지 확인
            if (isValid(rotated)) {
                count++
            }
        }
        return count
    }
}
```

## 문제 2. 짝지어 제거하기

### 설명

알파벳 소문자로 구성된 문자열에서 같은 문자열이 2개 붙어 있는 짝을 찾습니다. 짝을 찾은 다음에는 그 둘을 제거한 뒤 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성하세요. 성공적으로 수행할 수 있으면 1을, 아니면 0을 반환해주면 됩니다.

### 제약 조건

* 문자열의 길이 : 1,000,000 이하의 자연수
* 문자열은 모두 소문자로 이루어져 있습니다.

### 입출력의 예

| s      | result |
| ------ | ------ |
| baabaa | 1      |
| cdcd   | 0      |

### 코드

```kotlin
fun main() {
    fun solution(s: String): Int {
        // 연결된 문자를 넣을 스택 정의
        // 이전 문자열을 저장할 변수 정의 후 빈문자열 저장
        // 변환 문자열을 저장할 변수 정의 후 원본 문자열 저장
        // 변환 문자열이 빈 문자열이 아니고 이전 문자열과 변환 문자열이 동일하지 않을 때 까지 무한 반복
        //  이전 문자열에 변환 문자열 저장
        //  변환 문자열 순회
        //      스택의 첫 번째 문자가 존재하는지 확인
        //          존재하지 않을 경우
        //              스택에 현재 문자를 추가
        //              다음 문자로 이동
        //          존재할 경우
        //              스택의 첫 번째 문자와 현재 문자가 동일한지 확인
        //                  동일할 경우
        //                      스택에서 문자 제거
        //                      다음 문자로 이동
        //                  동일하지 않을 경우
        //                      스택에 현재 문자 추가
        //                      다음 문자로 이동
        //  변환 문자열에 스택에 쌓인 문자들로 문자열 만든 후 저장
        //  스택 초기화
        // 변환 문자열이 빈 문자열일 경우 1을 빈 문자열이 아닐 경우 0을 반환
        var stack = Stack<Char>()
        var before = ""
        var after = s
        while (after.isNotEmpty() && before.equals(after).not()) {
            before = after
            for (current in after) {
                if (stack.isEmpty()) {
                    stack.push(current)
                } else {
                    if (stack.peek() == current) {
                        stack.pop()
                    } else {
                        stack.push(current)
                    }
                }
            }
            after = stack.joinToString("")
            stack.clear()
        }
        return if (after.isEmpty()) 1 else 0
    }

    println(solution("cdcd"))
}
```

## 참고

{% embed url="<https://school.programmers.co.kr/learn/courses/30/lessons/76502?language=kotlin>" %}
괄호 회전하기
{% endembed %}

{% embed url="<https://school.programmers.co.kr/learn/courses/30/lessons/12973>" %}
짝지어 제거하기
{% endembed %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmyblog.gitbook.io/jimmys-blog/jimmys-tech/data-structure/stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.