# 연습 문제

## 개념 확인

### 스택과 큐에서 무엇이 먼저 나오는가

빈 스택 `S`와 빈 큐 `Q`를 준비하고, 각각에 같은 연산을 수행한다.

1단계: `A`를 넣는다.
2단계: `B`를 넣는다.
3단계: 원소 하나를 꺼내 기록한다.
4단계: `C`를 넣는다.
5단계: 비어 있을 때까지 원소를 계속 꺼내 기록한다.

`S`와 `Q`에서 원소가 나오는 순서를 각각 적고, ‘후입선출’ 또는 ‘선입선출’로 차이를 설명하라.

??? success "참고 답안"

    스택 `S`에서 나오는 순서는 `B, C, A`다. `A, B`를 넣은 뒤 가장 최근에 넣은 `B`를 먼저 꺼내고 `C`를 넣는다.
    이후 `C, A`를 차례대로 꺼내므로 ‘후입선출’의 특성을 보인다.

    큐 `Q`에서 나오는 순서는 `A, B, C`다. `A, B`를 넣은 뒤 가장 먼저 넣은 `A`를 꺼내고,
    `C`를 넣는다. 이후 `B, C`를 차례대로 꺼내므로 ‘선입선출’의 특성을 보인다.

### 큐의 뒤가 배열의 끝을 넘어가면 어떻게 되는가

길이가 5인 원형 배열로 큐를 구현하며, 배열의 인덱스는 `0～4`다.
현재 `front = 3`, `size = 2`이고 큐의 `A, B`는 각각 인덱스 3과 4에 있다.

<!-- numbered-subquestions -->

1. ‘`C`를 큐에 넣기’를 수행하면 `C`를 어느 인덱스에 저장해야 하는가? 삽입 후 `size`는 얼마인가?
2. 이어서 큐에서 한 번 꺼내면 어떤 원소가 나오는가? 새로운 `front`와 `size`는 각각 얼마인가?
3. 이때 큐의 앞에서 뒤로 이어지는 논리적 순서는 무엇인가? 원소를 꺼낼 때 배열의 다른 원소도 이동해야 하는가? 이유를 설명하라.

??? success "참고 답안"

    1. 새 원소의 위치는
        `(front + size) % 5 = (3 + 2) % 5 = 0`이므로,
        `C`는 인덱스 0에 저장된다. 삽입 후 `size = 3`이다.

    2. 현재 큐의 맨 앞 원소인 `A`가 나온다. 새로운 맨 앞 인덱스는
        `(3 + 1) % 5 = 4`이므로 `front = 4`, `size = 2`다.

    3. 유효한 원소의 논리적 순서는 `B, C`이며, `B`는 인덱스 4에, `C`는 인덱스 0에 있다.
        원소를 꺼낼 때는 `front`를 이동하고 `size`만 수정하면 된다. 원형 배열에서는 나머지 연산으로 인덱스가 처음으로 돌아가므로,
        다른 원소를 모두 앞으로 옮길 필요가 없다.

### 덱의 양 끝 연산

여기서는 `push_first`를 앞에 넣기, `push_last`를 뒤에 넣기,
`pop_first`를 앞에서 꺼내기, `pop_last`를 뒤에서 꺼내기로 정의한다.

빈 덱 `deq`에 다음 연산을 차례대로 수행한다.

1. `push_last(A)`
2. `push_last(B)`
3. `push_first(C)`
4. `pop_last()`
5. `push_last(D)`
6. `pop_first()`

<!-- numbered-subquestions -->

1. 두 번 꺼낸 원소는 각각 무엇인가?
2. 모든 연산을 마친 뒤 앞에서 뒤까지 어떤 원소가 남는가?
3. 뒤에서만 넣고 앞에서만 삭제할 수 있는 큐로 이 6단계를 모두 수행할 수 있는가? 불가능하다면 수행할 수 없는 연산을 찾아라. 이어서 덱은 모두 수행할 수 있는지와 그 이유를 설명하라.

??? success "참고 답안"

    처음 세 단계를 마치면 덱의 앞에서 뒤까지는 `[C, A, B]`다.

    <!-- numbered-subquestions -->

    1. `pop_last()`로 `B`를 꺼낸다. `D`를 넣으면 `[C, A, D]`가 되고,
        `pop_first()`로 `C`를 꺼낸다.

    2. 마지막에는 `[A, D]`가 남는다.

    3. 뒤에서만 넣고 앞에서만 삭제하는 큐로는 모든 연산을 수행할 수 없다.
        3단계의 `push_first(C)`는 앞에 넣어야 하고, 4단계의 `pop_last()`는 뒤에서 삭제해야 하므로 이 큐가 지원하는 연산 범위를 벗어난다.
        덱은 양 끝에서 모두 삽입과 삭제가 가능하므로 6단계를 전부 수행할 수 있다.

## 프로그래밍 연습

### 괄호 문자열 검사하기

세 종류의 괄호 `()`, `[]`, `{}`만 포함하는 문자열 `s`가 주어진다. 스택을 사용하여 올바른 괄호 문자열인지 판단하라.

올바른 문자열은 다음 두 조건을 모두 만족해야 한다. 닫는 괄호는 가장 최근에 등장한, 아직 짝이 없는 여는 괄호와 종류가 같아야 하며,
순회를 마친 뒤 짝이 없는 여는 괄호가 남아 있어서는 안 된다. 판단 결과를 불리언 값으로 반환하라.

??? tip "풀이 힌트"

    1. ‘닫는 괄호에서 대응하는 여는 괄호로의 매핑’을 만들 수 있다.
    2. 닫는 괄호를 만나면 먼저 스택이 비었는지 확인한 뒤 맨 위 괄호가 짝이 맞는지 확인한다.
    3. 순회가 끝난 뒤에도 스택이 비어 있어야 한다.

[LeetCode](https://leetcode.com/problems/valid-parentheses/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }