Stack, Queue, Deque

Stack은 LIFO

QUEUE는 FIFO 

기억하자! 

 

백준 28278번 

 

해당 코드. sys.stdin을 사용하는것이 굉장히 중요하다. 

 

기억할점 

pop은 변수로 받아서 사용해야 한다. (print(answerlist.pop))시 이상한 수가 나온다 .

 

파이썬은 stack이나 queue가 따로 없다.

 

파이썬의 pop은 가장 마지막 애를 제거한다 (LIFO) 즉, STACK이다파이썬의 POP(0)는, 가장 처음 애를 제거한다 (FIFO)즉, QUEUE이다.  

 

백준 4949번. 

import sys

#LIFO STACK !

while True :

    a = sys.stdin.readline().rstrip()

    stack = []

    if a == "." :

        break

    for i in a :

        if i == '[' or i == '(' :

            stack.append(i)

        elif i == ']' :

            if len(stack) != 0 and stack[-1] == '[' :

                stack.pop() # 맞으면 지워서 stack을 비워줌 0 = yes

            else :

                stack.append(']')

                break

        elif i == ')' :

            if len(stack) != 0 and stack[-1] == '(' :

                stack.pop()

            else :

                stack.append(')')

                break

    if len(stack) == 0 :

        print('yes')

    else :

        print('no')

 

중간에, 생각이 꼬이고 꼬여서 문제가 있었다.

답을 보고나서야 rstrip()를 하지 않음을 깨달았다..  

 

sys.stdin.readline() //or rstrip()은 문자열 형태로, 

sys.stdin.readline().split()은 빈칸단위 list 형태로 

list(map(str,sys.stdin.readline().split()))은 h,e,l,l,o로 변경함을 기억하자 

 

백준 12789번 

import sys

linever2 = []

linereal = []

N = int(sys.stdin.readline())

lineoriginal = list(map(int,sys.stdin.readline().split()))

x= 0

while (len(lineoriginal) != 0 ) :

    #한명씩 나간다 .

    x = lineoriginal.pop(0) #맨 앞에 나간다

    if x == 1 and (len(linereal) == 0 ):

        linereal.append(x)

        continue

    elif x != 1 :

        if len(linereal) == 0 : #아직 순서대로 없는데, 나온애가 1이 아님. -> 대기로

            linever2.append(x)

            continue

        elif linereal[-1] +1 == x:

            linereal.append(x)

            continue

        else :

            linever2.append(x)

            continue

        #순서대로가 있는데, 순서가 안맞음

    else :

        linever2.append(x)

 

# 다 나가고 나서, 남은 linever2가 하나씩 넣었을때 맞으면 ok 아니면 no

y=0

while (len(linever2) != 0) :

   y = linever2.pop()

   if y == linereal[-1]+1 :

      linereal.append(y)

   else :

       break

       

if (len(linever2) == 0 )  :

    #중도에 나와서 linever2가 남아

    print("Nice")

else :

    print("Sad")

 

내가 작성한 코드이다. 종이를 뒤져가며 모든 경우를 봤다고 생각했지만.. 보지 못한 case가 있는 것 같다.

 

## 추가 !! 

stack에서 (linever2)에서 바로 나갈 수도 있음을 몰랐다.. brute force는 정말 위험한 풀이가 맞는 것 같다. 

 

*이렇게 brute force식으로 풀려는 습관을 버려야 겠다.. 모든 case를 보지 못하는 경우가 많은것같다.

 

풀이를 찾아보니 - 주로 waiting에서 한번, 그 다음에 stack에서 찾는 경우로 많이 풀었다 

(반드시 1~n까지가  입력되기 때문)

 

import sys

N= int(sys.stdin.readline())

waiting = list(map(int,sys.stdin.readline().split()))

stack = []

target = 1

while (waiting) :

    if waiting[0] == target :

        waiting.pop(0)

        target = target+1

    else :

        stack.append(waiting.pop(0))

    while (stack) :

        if stack[-1] == target :

            x = stack.pop()

            target = target +1

        else :

            break

if (len(waiting) or len(stack)) != 0 :

    print("Sad")

else :

    print("Nice")

 

이후 과정은 쉽지만, 처음waiting에 넣고 조건에 맞아 pop한 이후에,  이에 break를 추가했던 실수를 했다.

이렇게 break를 하면 stack을 보지 않고 내려가서 문제가 생겼다. 

해당 과정을 주의하자 . 

 

백준 2346

파이썬에.. deque가 존재했다.

심지어는 deque중 회전에 대한 코드도 가능했다. 

 

import sys
from collections import deque

n = int(sys.stdin.readline())

deq = deque(enumerate(map(int, sys.stdin.readline().split()), start=1))
for i in range(n):
	p = deq.popleft() # pop(0)과 같은 결과를 가져오지만, pop(0)보다 더 빠르다
	print(p[0], end=' ')
	if p[1] > 0:
		deq.rotate(-(p[1] - 1)) # popleft된 1칸을 제외하고 시계 반대방향으로 회전
	else:
		deq.rotate(-p[1])

 

기억해야 할것 

1. from collections import deque

2. deq = deque(enumerate(map(int,sys.stdin.readline().split()), start =1 )) // 시작 index를 1부터 넣겠다는 의미 . 

(1,3),(2,4)... 이런식으로 들어간다.

3. deq.popleft() or deq. pop(0) -> (1,3)이런 형태가 나올것이다. 

4. 만약에 p[1] > 0 -> 양수 이면, 

deq. rotate(-(p[1] -1)) -> 시계 반대 방향으로 (뽑은숫자 - 나가는 숫자 제외) 만큼 이동

가장 위의 p가 제외되어서, 한개가 줄었고, 가장 위에있는 값이 그 다음것이 되었기 때문

5. 만약에 p[1]<0 이면, 

deq.rotate (-p[1]) -> 반대는 그만큼만 이동

 가장 위의 값이 그 다음것이 되었고, 이는 index+1인 형태이므로 반대로 돌리면 된다. 

 

deq. rotate(음수) -> 시계 반대방향으로 돌고, 맨위에 나갈애가 바뀐다. 

 

deque는, que처럼 fifo임에 주의하자.

pop(), popleft(). append(),appendleft()가 있다. 

 

백준 24511번 

 

내가 작성했던 코드  . 

하지만 시간 복잡도가 o(mn)이 되고, 제한이 1이 었기 때문에 틀린 답이 나오고 말았다. 

 

import sys

from collections import deque

n = int(sys.stdin.readline())

list_a = list(map(int, sys.stdin.readline().split()))  

list_b = list(map(int, sys.stdin.readline().split()))  

m = int(sys.stdin.readline())

list_c = list(map(int, sys.stdin.readline().split()))

res = deque()

for qs in range(n):

    if list_a[qs] == 0: #queue라면 . queue로만 이루어진 것 구성.

        res.appendleft(list_b[qs]) #1 4 시 , 4 1 로 이루어지게 . 

       

for i in range(m):

    res.append(list_c[i]) #append가 맨뒤만 되므로, 거꾸로 된 queue 생성! 

    print(res.popleft(), end=' ')

 

조금 더 침착했으면 좋았을것 같다. 

stack은 lifo라서 넣는게 의미 없는것 까진 인지하였으나, 

queue만으로 queue를 만들면 해결된다는 생각까지는 못했다. 

 

1. index와 value를 모두 기억하는 자료구조를 만들고 싶다면?

    queue =  [(i,p) for i,p in enumerate(priorities)]

 

priorties라는 array의 index(i)와 , value(p)를 받아와 [i,p]형태로 queue에다 대입한다,

 

2. 그 이후에, queue안의 값들 (queue[x][1])들과 비교하고 싶다면? any

if any(firstone[1] < p[1] for p in queue) :

 any (비교, for 각 행)을 통해, 각 행별로 비교가 가능하다.