스택, 큐, 덱

2346: 풍선 터뜨리기

문제

예제

나의 풀이

deque.rotate()를 사용하면 나름 간단하게 풀 수 있는 문제였다.

from collections import deque

n = int(input())
balloon = deque(enumerate(map(int, input().split())))
result = []

while balloon:
    idx, turn = balloon.popleft()
    result.append(idx+1)
    
    if turn > 0:
        balloon.rotate(-(turn-1))
    else:
        balloon.rotate(-turn)
        
print(' '.join(map(str,result)))

다른 풀이

deque.rotate()를 사용하지 않는 풀이다. turn > 0이면 앞의 숫자를 pop해서 리스트 뒤에 붙이고, turn <0이면 뒤의 숫자를 pop해서 리스트 앞에 붙이는 방식으로 리스트를 회전한다.

from collections import deque

n = int(input())
balloon = deque(enumerate(map(int, input().split())))
result = []

while balloon:
    idx, turn = balloon.popleft()
    result.append(idx + 1)

    if balloon:  # 풍선이 남아 있을 때만 이동 수행
        if turn > 0:
            # 오른쪽 이동: 현재 위치 기준으로 (turn-1)번 pop + append
            for _ in range(turn - 1):
                balloon.append(balloon.popleft())
        else:
            # 왼쪽 이동: (-turn)번 right-pop 후 left-insert
            for _ in range(-turn):
                balloon.appendleft(balloon.pop())

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

24511: queuestack

문제

예제

나의 풀이

문제 푸는 것보다 문제를 이해하는 게 더 어려웠다.... 😇

N은 queuestack을 구성하는 자료구조의 개수,
A는 i번 째 자료구조가 큐인지 스택인지 숫자를 통해 구분,
B는 i번 째 자료구조에 들어있는 초기값,
M은 기존에 있는 자료구조(B)에 삽입할 데이터의 길이,
C는 길이 M의 데이터라고 생각하고 문제를 풀었다.

예제 입력 1을 예시로 풀이 아이디어를 설명하자면, queu는 선입후출, stack은 선입선출이기 때문에 사실상 stack에 append()로 들어간 데이터는 pop() 연산으로 나오게 되어 있어서 순서에 전혀 영향을 주지 않는다.
아래 이미지를 보면 파란색 숫자가 삽입된 데이터, 흰 숫자가 자료구조에 들어있는 초기값 즉,B[i]이다. stack에 들어간 데이터는 그대로 나오지만, queu는 데이터가 앞으로 들어가고(appendleft()) 나가는 건 마지막 데이터가 나가기 때문에(pop()) 순서에 영향을 주게 된다.
따라서 queu만 모아서 연산을 하면 결과값을 얻을 수 있다.

정답 코드

from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = int(input())
c = list(map(int, input().split()))

q = deque()
# 스택은 선입선출 구조를 가지고 있어서 결과에 영향을 주지 않음
for i in range(n):
    if a[i] == 0: # 큐인 자료구조만 모으기
        q.append(b[i]) #i번 자료구조에 들어있는 원소 즉, 초기값 세팅

for i in range(m):
    q.appendleft(c[i])
    print(q.pop(), end =' ')

끄적끄적

deque.rotate()

deque.rotate(n)는 deque의 원소를 회전시키는 기능을한다.
오른쪽(n > 0)으로 회전하면 마지막 원소가 앞으로 이동한다.
왼쪾(n < 0)으로 회전하면 첫 번째 원소가 뒤로 이동한다.

오른쪽으로 회전(n > 0)

from collections import deque

dq = deque([1, 2, 3, 4, 5])
dq.rotate(2)  # 2칸 오른쪽으로 회전
print(dq) # deque([4, 5, 1, 2, 3])

왼쪽으로 회전(n < 0)

dq = deque([1, 2, 3, 4, 5])
dq.rotate(-2)  # 2칸 왼쪽으로 회전
print(dq) # deque([3, 4, 5, 1, 2])

n이 길이보다 큰 경우
길이로 나눈 나머지만큼 회전한다.

dq = deque([1, 2, 3, 4, 5])
dq.rotate(7)  # 길이(5)보다 큰 7로 회전
print(dq) # deque([4, 5, 1, 2, 3])

백준 단계별로 풀어보기 끝 !

알고리즘을 공부하면서 단계별 문제를 풀면 코딩테스트 실력이 늘 수 있지 않을까 싶어서 시작했던 나만의 하루 5문제 챌린지 였는데, 드디어 끝났다.
사실 어려운 문제를 만나면 한 문제 푸는데도 많은 시간이 걸려서 5문제 풀기가 쉽지 않은 날도 있었는데 이렇게 목표한 바를 이루고 나니까 뿌듯하고 코딩 실력도 전보다 훨씬 향상된 것 같다.
이제는 하루 2문제 정도씩만 풀면서 모르는 내용만 포스팅하고 SQL 코테도 같이 준비해야겠다.
3월도 화이팅 😆😆😆