Koala 5주차 : 스택, 큐, 데큐, 우선순위 큐

1. 스택(Stack)

후입선출 구조로써 한쪽 구멍만 있는 통 안에 물건을 집어넣고 빼는 형식이다.

 

 

 

* 관련 문제

1. 1874 : 스택 수열

https://www.acmicpc.net/problem/1874

 

import sys
input = sys.stdin.readline

count = 1
temp = True
op = []
stack = []

for i in range(int(input())):
    n = int(input())
    while n>=count:
        stack.append(count)
        count += 1
        op.append('+')
    
    if stack[-1] == n:
        op.append('-')
        stack.pop()
    else:
        temp = False
        break

if temp:
    for i in op:
        print(i)
else:
    print('NO')

 

 

스택 관련된 문제를 풀이하다보면 while의 중요성을 조금씩 깨달아가고 있는 것 같다. stack은 리스트로 된 형태를 가지는데 그러다보면 시간 복잡도 측면에서 while을 얼마나 잘 활용하나가 문제 풀이의 중심이 되는 것 같다.

 

 

 

 

 

 

 

 

2. 17298 : 오큰수

음 솔직히 엄청 쉬울 줄 알았는데 이중 for문 밖에 생각이 안나서 시간초과가 뜰 것 같았다. 도무지 stack을 써서 할 방법은 생각이 나지 않아서 블로그를 참고했다.

 

https://hongcoding.tistory.com/40

[백준] 17298번 오큰수 (Python 파이썬)

 

 

블로그를 봐도 오큰수를 구하는 방법이 짧은 코드 줄에 비해서 직관적으로 와닿지는 않았던 것 같다.

코드 시각화 사이트를 보고 한줄씩 돌려보고 나서야 이해할 수 있었다. stack으로 index 정보를 저장해서 갱신할 수와 index 정보들을 토대로 답을 구해는 과정이었다.

stack을 이중 for문을 쓰지 않기 위해서 index 저장으로 쓴 점과 위의 문제와 마찬가지로 while문의 중요도를 알 수 있었다.

 

 

 

import sys
input = sys.stdin.readline


n = int(input())
list1 = list(map(int, input().split()))
nge = [-1]*n
stack = [0]

for i in range(1,n):
    while stack and list1[stack[-1]]<list1[i]:
        nge[stack.pop()] = list1[i]
    stack.append(i)

print(*nge)

 

 

 

 

 

 

 

 

3. 12789 : 도키도키 간식꾸러미

 

 

 

 

 

 

2. 큐(Queue)

 

한 쪽에서는 삽입만, 다른 한 쪽에서는 삭제만 가능한 자료구조.

큐는 가장 먼저 들어온 요소가 가장 먼저 나가는 선입선출(FIFO,First In First Out)의 특징을 가지는 자료구조이다. 터널을 연상하면 더 쉽게 이해할 수 있다.

 

한 쪽으로만 들어올 수 있는 건 스택과 동일하지만, 다른 쪽으로 나가야 한다는 것이 스택과 차별화된 큐의 특징임.

 

 

 

* 관련 문제

 

1. 1966 : 프린터 큐

 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n,m = map(int,input().split())
    list1 = list(map(int, input().split()))
    check = [False for _ in range(n)]
    check[m] =True
    count = 0

    while True:
        if list1[0]>=max(list1):
            count += 1
            if check[0] == True:
                print(count)
                break
            else:
                list1.pop(0)
                check.pop(0)
        else:
            list1.append(list1.pop(0))
            check.append(check.pop(0))

 

 

이번 문제도 while문을 얼마나 잘 쓰냐의 문제였다. queue는 가장 앞에 있는 요소가 빠지고 추가될 때는 가장 뒤에서 추가되므로 가장 앞에 있는 요소만 비교하는 것이 이문제의 핵심이었다.

 

 

 

 

 

 

 

 

 

3. 데큐(deque)

 

* 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조

+) deque에는 기본적인 함수 4개(append(), appendleft(), pop(), popleft())가 있다.

 

 

*  관련 문제

1. 1835 : 카드

 

import sys
input = sys.stdin.readline

from collections import deque

n = int(input())
dq = deque()

for i in range(n, 0, -1):
    dq.appendleft(i)
    for j in range(i):
        dq.appendleft(dq.pop())

print(*dq)

 

 

문제를 잘못 이해해서 해결하는 데 꽤 오랜 시간이 걸렸다. for문을 돌때 i번 만큼 리스트 오른쪽의 원소를 왼쪽으로 삽입하면 되는 문제였다.

 

 

 

 

 

 

 

 

4. 우선순위 큐(priority queue)

 

* FIFO의 특징을 가진 큐(queue)에 우선순위 방식을 접목시킨 자료구조이다.

+) 우선순위 큐는 힙(heap)이라는 자료구조를 통해 구현할 수 있다!

 

 

힙의 종류에는 최대 힙과 최소 힙이 있으며 각각 c++에서는 최대 힙을, python에서는 최소 힙이 default임.

 

 

우선순위 큐를 이용해서 리스트를 힙으로 추가하고 삭제하고 정렬하는 방식이 있는데,

1. heappush  -> 요소가 추가되면 요소들이 최소 힙으로 정렬된다.

2. heappop    -> 요소들이 삭제되면 요소들이 최소 힙으로 정렬된다.

3. heappify    ->  요소들이 최소 힙을 정렬된다.

 

내가 주로 쓰는 언어는 파이썬이기 때문에 파이썬 default가 최소 힙이라 최소 힙으로 정렬된다. 

 

 

 

 

 

 

* 관련 문제

 

1. 1927 : 최소 힙

 

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

x = int(input())
hq = []

for _ in range(x):
    num = int(input().strip())
    if num != 0:
        heappush(hq,num)

    else:
        if not hq:
            print(0)
        else:
            print(heappop(hq))

 

heap 자료구조를 만들어주고, heappush와 heappop을 적절히 잘 이용하면 되는 문제였다.