<스택2>
import sys
stack = []
n = int(sys.stdin.readline())
for _ in range(n): # 5가지 명령에 대한 코드 작성
command = sys.stdin.readline().split()
if command[0] == '1':
stack.append(command[1])
elif command[0] == '2':
if stack:
print(stack.pop())
else:
print(-1)
elif command[0] == '3':
print(len(stack))
elif command[0] =='4':
if stack:
print(0)
else:
print(1)
elif command[0] == '5':
if stack:
print(stack[-1])
else:
print(-1)
☆ if stack : 파이썬에서 스택이 비어있는지 확인 → 스택에 뭐가 있으면 True, 비어 있으면 False
☆ if command[0] == '1' : command[0]의 값을 확인할 때 정수가 아니라 문자열로 비교해야함. 왜냐하면 sys.stdin.readline().split()은 command를 문자열로 분리한 리스트로 반환하기 때문이다. 따라서 조건문을 작성할 때 문자열로 작성해야함
☆ 스택은 LIFO이므로 마지막에 추가된 요소가 가장 먼저 제거된다. stack[-1]은 리스트의 마지막 요소(가장 맨 위에 있는 요소)를 의미한다.
☆ for _ in range(N) 에서 _는 단순히 반복 횟수를 세기 위한 변수로 값이 필요하지 않을 때 관례적으로 사용되는 표현.
_ 대신 i를 넣어도 되지만 i값을 사용하지 않기 때문에 불필요한 변수 선언이 된다.
<10773번 : 제로>
# 스택을 이용하면 될 듯
import sys
st = [] # 빈 스택
k = int(sys.stdin.readline())
for i in range(k):
num = int(input())
if num == 0:
st.pop()
else:
st.append(num)
total = 0
for i in st:
total += i
print(total)
-풀었음
☆ 스택 이용하기
[두번째 풀이_sum함수 이용]
# 스택 이용
import sys
K = int(sys.stdin.readline())
st = []
for _ in range(K):
num = int(sys.stdin.readline())
if num == 0:
st.pop()
else:
st.append(num)
print(sum(st))
<4949번 : 균형잡힌 세상>
while True:
a = input()
st = [] # 괄호를 추가할 리스트 스택
if a == ".":
break # .이 들어오면 종료
for i in a:
if i == '[' or i == '(':
st.append(i)
elif i == ']':
if len(st) != 0 and st[-1] == '[':
st.pop() # 맞으면 지워서 스택을 비워줌
else:
st.append(']')
break
elif i == ')':
if len(st) != 0 and st[-1] == '(':
st.pop()
else:
st.append(')')
break
if len(st) == 0:
print('yes')
else:
print('no')
<18258번 : 큐 2>
# 큐
import sys
from collections import deque
N = int(sys.stdin.readline())
queue = deque([])
for i in range(N):
com = sys.stdin.readline().split()
if com[0] == 'push':
queue.append(com[1])
elif com[0] == 'pop':
if len(queue) == 0:
print(-1)
else:
print(queue.popleft())
elif com[0] == 'size':
print(len(queue))
elif com[0] == 'empty':
if len(queue) == 0:
print(1)
else:
print(0)
elif com[0] == 'front':
if len(queue) == 0:
print(-1)
else:
print(queue[0]) # 맨 앞 정수 출력
elif com[0] == 'back':
if len(queue) == 0:
print(-1)
else:
print(queue[-1])
☆ from collections import deque
[if문 조금 다르게]
import sys
from collections import deque
qu = deque()
N = int(sys.stdin.readline())
for _ in range(N):
com = sys.stdin.readline().split()
if com[0] == 'push':
qu.append(com[1])
elif com[0] == 'pop':
if qu:
print(qu.popleft()) # 가장 앞에 있는 정수 빼기
else:
print(-1)
elif com[0] == 'size':
print(len(qu))
elif com[0] == 'empty':
if qu:
print(0)
else:
print(1)
elif com[0] == 'front':
if qu:
print(qu[0]) # 맨 앞 정수 출력
else:
print(-1)
elif com[0] == 'back':
if qu:
print(qu[-1])
else:
print(-1)
<2164번 : 카드2>
[덱 이용]
from collections import deque
N = int(input())
deque = deque([i for i in range(1, N+1)])
while(len(deque) > 1): # 큐에 카드가 한 장 남을 때까지 반복
deque.popleft() # 큐의 가장 왼쪽(가장 위에 있는) 카드 제거
move_num = deque.popleft() # 그 다음으로 가장 왼쪽에 있는 카드를 꺼내어 move_num에 저장
deque.append(move_num) # 방금 꺼낸 move_num을 큐의 맨오른쪽(가장 아래)에 다시 추가
print(deque[0]) # deque[0]은 큐의 가장 왼쪽에 남은 마지막 카드
☆ 이 문제의 포인트는 queue와 deque 중에서 뭘 사용해야할지 결정하는 것 → 큐를 이용하면 시간 초과
☆ 덱을 이용한 위 코드의 시간복잡도는 O(N)이다. N개의 카드가 있을 때, n-1번의 반복문을 실행하게 되기 때문이다. 이 문제에서 최악의 경우 시간 복잡도가 O(N^2)인 경우도 있다. 이는 deque를 사용하면 최악의 경우에도 O(n)이 되므로 덱을 사용해서 효율적으로 풀어야한다.
<11866번 : 요세푸스 문제0>
from collections import deque
N, K = map(int, input().split())
qu = (deque([i for i in range(1, N+1)]))
# 요세푸스 순열 생성
y = [] # 제거된 사람의 순서를 저장하는 리스트
while len(qu) != 0: # 덱에 사람이 남아 있을 때까지 반복
for _ in range(K-1):
qu.append(qu.popleft()) # 덱의 맨 앞 사람을 꺼내어 맨 뒤로 보내는 작업
y.append(str(qu.popleft())) # K번재 사람을 제거하고 이를 y에 추가
print('<'+', '.join(y)+'>') # 출력조건에 맞게 출력
- for _ in range(K-1) : K-1번 동안 덱의 맨 앞에 있는 사람을 맨 뒤로 이동시킨다. 이는 K번째 사람을 찾기 위해 K-1번 이동하는 과정을 의미
<28279번 : 덱2>
import sys
from collections import deque
N = int(sys.stdin.readline())
d = deque()
for _ in range(N):
cmd = list(map(int, sys.stdin.readline().strip().split()))
if cmd[0] == 1:
d.appendleft(cmd[1]) # 덱의 앞에 넣는다.
elif cmd[0] == 2:
d.append(cmd[1]) # 덱의 뒤에 넣는다.
elif cmd[0] == 3:
if d:
print(d.popleft())
else:
print(-1)
elif cmd[0] == 4:
if d:
print(d.pop()) # 맨 뒤의 정수를 빼고 출력한다.
else:
print(-1)
elif cmd[0] == 5:
print(len(d))
elif cmd[0] == 6:
if d:
print(0)
else:
print(1)
elif cmd[0] == 7:
if d:
print(d[0]) # 맨 앞 정수 출력
else:
print(-1)
elif cmd[0] == 8:
if d:
print(d[-1]) # 맨 뒤 정수 출력
else:
print(-1)
- 풀었음
☆ map객체는 인덱싱이 불가하기 때문에 입력 받을 때 list로 바꿔줘야함
☆ strip()은 안 써줘도 되지만 split()은 꼭 써줘야 문제 조건에 부합함!
<2436번 : 풍선 터뜨리기>
import sys
from collections import deque
input=sys.stdin.readline
N = int(input())
q = deque(enumerate(map(int, input().split())))
ans = []
while q:
idx, paper = q.popleft()
ans.append(idx+1)
if paper > 0:
q.rotate(-(paper-1))
elif paper < 0:
q.rotate(-paper)
print(' '.join(map(str, ans)))
☆ enumerate : 터진 풍선의 '번호(인덱스+1)'를 출력하는 문제이므로 pop을 하더라도 초기 인덱스 정보는 끝까지 유지되어야 한다. 이를 위해 enumerate 사용.
- enumerate 사용 전 : deque([3,2,1,-3,-1])
- enumerate 사용 후 : deque([(0,3),(1,2),(2,1),(3,-3),(4,-1)]) → 덱에 인덱스와 종이 값이 튜플로 묶여서 하나의 원소로 저장된다. 따라서 idx, paper = q.popleft()를 하면 idx에는 0이, paper에는 3이 저장된다.
☆ deque.rotate() : rotate(-1)은 원형 큐를 반시계방향으로 1칸 회전시키고, rotate(1)은 시계방향으로 1칸 회전시킨다.
- ans는 터진 풍선의 순서를 저장하는 리스트
- while q : 덱이 비어있지 않은 동안 계속 실행
- q.popleft()를 사용해 덱의 맨 앞에서 풍선을 꺼내고, ans리스트에 풍선 번호(idx+1)를 추가한다.
-
[Python] 백준 2346 풍선 터뜨리기 (Deque)
터진 풍선의 '번호(인덱스+1)'를 출력하는 문제이므로 pop을 하더라도 초기 인덱스 정보는 끝까지 유지되어야 한다. 이를 위해 enumerate가 사용되었다. enumerate 사용 전과 후의 덱 상태를 비교해보자
velog.io
* deque.rotate() : 함수 안에 음수를 넣게 된다면 왼쪽 회전, 양수는 오른쪽 회전이다.