# [TIL] Algorithms Day 3 - Stack, Queue, Heap

# Problem 1. [Stack Permutation](https://www.acmicpc.net/problem/1874)

```python
N = int(input())

goal = []
stack = []
count = 0
result = []
compare_lst = []
can_stack = True

for i in range(N):
    val = int(input())
    goal.append(val)
    while val > count:
        result.append('+')
        count += 1
        stack.append(count)
    if val == stack[-1]:
        result.append('-')
        stack.pop()
    else:
        can_stack = False
        break

if can_stack == False:
    print('NO')
else:
    print('\n'.join([str(num) for num in result]))
```

# Problem 2. [Spinning Queue](https://www.acmicpc.net/problem/1021)

```python
from collections import deque

n, m = map(int, input().split())
targets = list(map(int, input().split()))
que = deque(i for i in range(1, n+1))
cnt = 0

for target in targets:
    while que[0] != target:
        if que.index(target) < round(len(que)) / 2: # this logic was hard & need to consider if the len(que) is odd or even number
            que.rotate(-1)
            cnt += 1
        else:
            que.rotate(1)
            cnt += 1
    que.popleft()

print(cnt)
```

* [deque library](https://docs.python.org/3/library/collections.html#deque-objects)
    

# Problem 3. [Parenthesis](https://www.acmicpc.net/problem/9012)

```python
N = int(input())

for _ in range(N):
    stack = 0
    gwalhos = input()
    for gwalho in gwalhos:
        if gwalho == '(':
            stack += 1
        if gwalho == ')':
            stack -= 1
        if stack < 0:
            break 
    if stack != 0:
        print('NO')
    else:
        print('YES')
```

* Cleaner Solution
    
    ```python
    N = int(input())
    for _ in range(N):
        S = input()
        while '()' in S:
            S = S.replace('()','')
        if S == '':
            print("YES")
        else:
            print("NO")
    ```
    

# Problem 4. [Balancing World](https://www.acmicpc.net/problem/4949)

```python
while True:
    sentence = input()
    stack = []
    flag = True

    if sentence == '.': # termination condition
        break

    for s in sentence:
        if s == '(' or s == '[':
            stack.append(s)

        elif s == ')':
            if len(stack) < 1:
                flag = False
                break
            if stack[-1] != '(':
                flag = False
                break
            stack.pop()
 
        elif s == ']':
            if len(stack) < 1:
                flag = False
                break
            if stack[-1] != '[':
                flag = False
                break
            stack.pop()

    if len(stack) != 0 or flag == False:
        print('no')
    else:
        print('yes')
```

# Problem 5. [Max Heap](https://www.acmicpc.net/problem/11279)

```python
import heapq, sys
heap = []
heapq.heapify(heap)
input = sys.stdin.readline
N = int(input())

for _ in range(N):
    i = int(input())
    if i == 0:
        if len(heap) < 1:
            print(0)
        else:
            print(-heapq.heappop(heap)) # put - sign to convert neg to pos
    else:
        heapq.heappush(heap, -i) # put - sign to make min heap to max heap
```

* [Heapq methods](https://docs.python.org/3/library/heapq.html)
    
* [Max Heap Implementation](https://www.techiedelight.com/max-heap-implementation-in-python-using-heapq/)
    
* `input()` vs `sys.stdin.readline` : [link](https://www.geeksforgeeks.org/difference-between-input-and-sys-stdin-readline/)