[Python] 백준 알고리즘 스택∙큐∙덱 기억할 것들

백준 28278 - 스택2

import sys

input = sys.stdin.readline

a = int(input())

stack = []

for i in range (a):

    inner = list(map(int, input().split()))

    if inner[0] == 1 :

        stack.append(inner[1])

    elif inner[0] == 2 :

        print(stack.pop() if len(stack) else -1)

    elif inner[0] == 3 :

        print(len(stack))

    elif inner[0] == 4 :

        print(1 if len(stack)==0 else 0)

    else :

        print(stack[-1] if len(stack)!=0 else -1)

➝ stack 전체를 구현해야한다는 압박 필요없이, 주어진 문제를 잘 분석할 것.

명령어 1을 처리하기 위해 명령어 입력 list로 받는다. (아니었으면 정수로 받았을 것)

✓ python에서는 null객체 사용 x 이다. 문제와 같이 len()으로 접근하거나 is none 등 사용한다.

 

 

☆ 백준 9012 - 괄호

import sys

input = sys.stdin.readline

a = int(input())

outer_stack = []

for i in range (a):

    word = input()

    stack = []

    success = 1

    for char in word :

        if char == '(' :

            stack.append(char)

        elif char == ')' :

            if len(stack) :

                stack.pop()

            else :

                success = 0

                break

   

    if len(stack) == 0 and success == 1 :

        outer_stack.append("YES")

    else :

        outer_stack.append("NO")

           

for i in outer_stack :

    print (i)

➝ 처음에는 단순히 갯수비교로만 생각했었으나, 순서와도 관련이 있다.

따라서 괄호에 대해 if else문 필요하고 ( ')'에 대해 elif가 아닌 그냥 else: 하면 답 안나옴 )

각각 상황에 success 여부로 값 따로 저장 안 하고 바로 출력하면 입력값 각각에 출력 나옴 (한번에 x)

따라서 문제에 따라 적절하게 잘 설정하기 ~

 

 

백준 4949 - 균형잡힌 세상

while True :

    stack = []

    s = input()

    success = 1

    if s == "." :

        break

    for i in s :

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

            stack.append(i)

        elif i == ')':

            if stack and stack[-1] == '(':

                stack.pop()

            else:

                success = 0

                break

        elif i == ']':

            if stack and stack[-1] == '[':

                stack.pop()

            else:

                success = 0

                break

    if len(stack)==0 and success == 1 :

        print("yes")

    else:

        print("no")

➝ 입력이 string이 아니라 char 이므로 마침표가 들어올 때 까지 입력받고 처리한다.

한 문장씩 처리함

 

 

백준 18258 - 큐2

import sys

from collections import deque

input = sys.stdin.readline

a = int(input())

queue = deque()

for i in range (a):

    command = list(input().split())

    if command[0] == 'push':

        queue.append(command[1])

    elif command[0] == 'pop':

        print(queue.popleft() if queue else -1)

    elif command[0] == 'size':

        print(len(queue))

    elif command[0] == 'empty':

        print(0 if queue else 1)

    elif command[0] == 'front':

        print(queue[0] if queue else -1)

    else:

        print(queue[-1] if queue else -1)

* 큐의 경우에만 pop연산시에 collections 라이브러리의 deque 사용하는것이 빠르다.

list로 연산하면 자리 전부 다시 정렬 등 해줘야하므로 deque의 popleft()를 통해 간단하게 해결 가능하다.

+ 간단한 내용들도 실수하지 않도록 주의

 

 

☆ 백준 11866 - 요세푸스 문제0

import sys

input = sys.stdin.readline

n, k = map(int, input().split())

a = [i for i in range (1, n+1)]

# a [1 2 3 4 5 6 7] 받음

b = []

idx = 0

while a :

    idx += k-1

    if idx >= len(a):

        idx %= len(a)

    b.append(a.pop(idx)) #pop이면 인덱스 값을, del이면 값을 삭제

print("<", end='')

print(', '.join(map(str,b)), end='')

print(">")

✓ 인덱스 값이 전체 리스트의 크기보다 커진다면 크기로 나눈다는 것**

✓ a.pop()이면 마지막 값을 제거, a.pop(1)이면 1번째 인덱스 값을 제거, a.del(1)이면 1값을 전부 제거

따라서 pop과 del의 사용방법 제대로 알고 풀어야 한다.

 

 

☆☆ 백준 2346 - 풍선 터뜨리기

import sys

from collections import deque

input = sys.stdin.readline

a = int(input())

value = deque(enumerate(map(int, input().split()))) #풍선 안의 종이 입력

result = []

while value :

       idx, paper = value.popleft() #enumerate로 선언했으니 idx에 인덱스값, paper에 해당 값 저장된다.

       result.append(idx+1)

 

       if paper>0:

       value.rotate(-(paper-1))

       elif paper<0:

       value.rotate(-paper)

print(' '.join(map(str,result)))

알아야 할 deque의 개념

① enumerate 

[h,e,l,l,o] 의 일반적인 deque를

[(0,h), (1,e), (2,l), (3,l), (4,o)] 와 같이 인덱스값까지 동시에 저장한다.

따라서 값 저장할 땐 a, b = 덱이름.pop() 등으로 받을 수 있다.

이 문제에서 가장 핵심적인 기능이다. pop된 이후에도 원래의 인덱스가 유지되어야하므로 일반 list등으로 구현하기에는 한계가 있다.

 

② rotate

rotate를 알기 전엔 idx값을 조절해서 원하는 값을 접근하려 했다.

이렇게 되니 idx<0, idx>=len(value) 등 고려해야할 사항이 많아 복잡했으나

idx와 풍선 내용값을 받는 위치를 고정하고 (popleft로 덱의 가장 앞)

deque.rotate 사용하니 위와같은 인덱스 고민이 사라졌다.

✓ paper > 0인 경우에는 바로 앞에 popleft된 값은 제외하고 왼쪽으로 rotate 

✓ paper < 0인 경우에는 -(-값) = +값으로 만들어서 오른쪽으로 rotate

 

+ ③ join → 리스트의 요소를 하나의 문자열로 바꾸어 반환해줌. 따라서 for문 사용하지 않아도 된다. + 구분자 결정도 가능하다. 

ex) ','.join(map(str,리스트)) → 출력 1,2,3,4 ... , ' '.join(리스트) → 출력 1 2 3 4 ... 

**문자열로 만들어버리는 것이므로 리스트 원소 int 아닌 str이 된다.

 

 

☆☆ 백준 24511 - queuestack

import sys

from collections import deque

input = sys.stdin.readline

 

#기존

n = int(input())

sorq = list(map(int, input().split()))

val = list(map(int, input().split()))

 

#추가

m = int(input())

add = list(map(int, input().split()))

 

#결과반환용도

result = deque()

for i in range (n):

      if sorq[i]==0:

            result.appendleft(val[i]) #큐 선입선출이므로 leftappend (주어진 값들 중 큐값만 유효하게 쓰인다.)

 

for i in add: #추가된 횟수만큼만 출력

      result.append(i) #마지막에 존재하는 큐에 대해서만 고려해주면 된다.

      print(result.popleft(), end=' ') #선입선출이므로 popleft

[문제이해]

1. 주어진 자료구조 [[큐], [스택], [스택], [*큐]] 가 있다. 

2. 각각의 큐 or 스택 에 할당된 값을 pop()해서 이웃한 다음 자료구조 큐 or 스택 에 삽입한다.

3. 마지막 자료구조 (주어진 문제에서는 *큐) 에서 pop된 값을 시간 순서대로 출력하기 (첫번째 pop된 값 > 두번째 pop ... > 세 ...)

 

⬇️ 예제 입력값

자료구조 개수 N	4
큐 or 스택 (큐 0 스택 1)	0 1 1 0
자료구조에 들어있는 원소 초기값	1 2 3 4
해당 자료구조에 추가할 값 개수	3
삽입할 원소들	2 4 7

 

⬇️ 예제 기반 자료구조 queuestack의 초기값 (추가 전)

큐 or 스택	큐 (0)	스택(1)	스택(1)	큐(0)
들어있는 값	1	2	3	4

 

----- 3개의 원소 2, 4, 7 삽입 -----

 

⬇️ 2 삽입

큐 or 스택	큐 (0)	스택(1)	스택(1)	큐(0)
들어온 값	2	1	1	1
들어있던 값	1	2	3	4
pop 되는 값	1	1	1	4

① 큐는 FIFO 이므로 2가 새로 들어왔지만 원래 있던 값인 1이 pop 되어 2번 자료구조인 스택으로 들어감.

② 스택은 LIFO 이므로 1이 새로 들어와서 들어온 그대로 1이 pop되어 3번 자료구조인 스택으로 들어감.

③ 스택이므로 1이 들어왔다가 그대로 다시 1이 pop되어 4번 자료구조인 큐로 들어감.

④ 큐이므로 1이 들어왔지만 원래 있던 값인 4가 pop되어 결과(최종 출력될 값)에 쌓이게 됨.

 

📍 여기서 알 수 있는 것 : 스택은 어차피 LIFO 이므로 원래 값과 관계없이 그냥 들어온 값 그대로 나감

  ∴ 스택은 무시 가능하다 !

예) 위 자료구조에서

A. 큐 → 스택 → 스택 → 큐  ==  1 → 1 → 1 → 4

B. 큐 → 큐 == 1 → 4

 

따라서 코드 계산 시 sorq[i] == 0 일 때 (큐일 때) 의 값만 결과에 appendleft(val[i]) 하면 된다.

* 출력은 4 ... 1 이 되는데, val[i]는 1 ... 4 순서대로 대입되므로 appendleft를 한다.

(실제 쌓이는 순서 고려)

 

2삽입 후 4, 7 삽입도 테이블로 표현하면

* 빨간색 == pop 되는 값

 

⬇️ 4 삽입

큐 or 스택	큐 (0)	스택(1)	스택(1)	큐(0)
들어온 값	4	2	2	2
들어있던 값	2	2	3	1
pop 되는 값	2	2	2	1

⇢ 스택 무시 가능함을 다시한번 확인

→ 배출되는 값 1 이므로 결과에 쌓이게 된다. 

 

⬇️ 7 삽입

큐 or 스택	큐 (0)	스택(1)	스택(1)	큐(0)
들어온 값	7	4	4	4
들어있던 값	4	2	2	2
pop 되는 값	4	4	4	2

→ 배출되는 값 2 이므로 결과에 쌓이게 된다. 

세번의 삽입 과정을 통해 순서대로 4 → 1 → 2 가 배출되었다. 

 

⬇️ 결과 리스트

2 넣어서 배출된 값 (마지막 pop)	4 넣어서 배출된 값 (마지막 pop)	첫번째로 추가된 값	두번째로 추가된 값	세번째로 추가된 값
4	1	2	4	7

원래 큐에있던 값 4, 1 다 나오고 (큐가 2개이니 2개 출력됨)

다음으로 추가된 값들이 차례로 배출될 것이다. (원래 큐에 들어있던 값들 다 빠지고, 새롭게 큐에 들어간 값들 st)

따라서 결과리스트의 결과리스트 세번째 값 부터는 추가된 값 차례로 넣어주면 된다 append(i) (i=2,4,7 ...)

 

여기에서 출력은 추가된 횟수 만큼만 이루어질 것이므로 최종 결과는 아래와 같다.

[결과] 4 1 2

 

(*나머지 4, 7도 출력되려면 기존의 큐 2개를 채울 또다른 값이 2개 들어와야한다.)