[백준/Python]스택, 큐, 덱 - part.2

문제

백준 단계별 풀이 - 스택, 큐, 덱

https://www.acmicpc.net/step/11

(모든 문제는 파이썬으로 풀이)

---

[18258]큐 2

문제링크: https://www.acmicpc.net/problem/18258

 

큐 구현 후 주어진 명령대로 처리하는 문제다.

 

단계별 풀이

먼저 나는 deque모듈을 사용했다.

deque는 O(1)의 속도, list는 O(n)의 속도를 지원한다.
그리고 Queue모듈은 멀티쓰레드 환경을 지원하기 때문에 deque보다 느리다.
=> 결론: 알고리즘 문제 풀 때는 deque!

from sys import stdin
from collections import deque


input = stdin.readline
N = int(input())
dq = deque()

• input 함수 제정의.
• 명령어의 갯수 N 할당.
• collections의 deque모듈을 이용하여 빈 덱 dq 생성.

for _ in range(N):
    command, *num = input().split()

    if command == "push":
        dq.append(int(num[0]))
    elif command == "size":
        print(len(dq))
    elif command == "empty":
        print(int(not len(dq)))
    elif len(dq) != 0:
        if command == "pop":
            print(dq.popleft())
        elif command == "front":
            print(dq[0])
        elif command == "back":
            print(dq[-1])
    else:
        print(-1)

• 명령어로 push 정수가 들어올 경우를 위해 공백으로 나눈 입력값을 command, *num으로 언패킹.
  (참고: https://5as2s.tistory.com/176#%5B28278%5D%EC%8A%A4%ED%83%9D%202-1)
• "pop", "front", "back"과 같은 명령어가 주어졌을경우, dq가 비어있는지 확인한다.
  • 비어있지 않다면 지시대로 명령어 수행.
  • 비어있다면 아래의 else문이 실행되며 -1을 출력한다.

 

전체 코드

# 메모리: 110548KB / 시간: 1884ms

from sys import stdin
from collections import deque


input = stdin.readline
N = int(input())
dq = deque()

for _ in range(N):
    command, *num = input().split()

    if command == "push":
        dq.append(int(num[0]))
    elif command == "size":
        print(len(dq))
    elif command == "empty":
        print(int(not len(dq)))
    elif len(dq) != 0:
        if command == "pop":
            print(dq.popleft())
        elif command == "front":
            print(dq[0])
        elif command == "back":
            print(dq[-1])
    else:
        print(-1)

---

[2164]카드 2

문제링크: https://www.acmicpc.net/problem/2164

 

버리고, 맨 뒤로 보내고, 버리고, 맨 뒤로, 버, 뒤, 버, 뒤...
그리고 가장 마지막에 남은 카드를 출력하기.

 

반복하는 문제다. 규칙이 있을것같지만 일단 작성해봤다.
(전체 코드 항목에 규칙을 이용한 풀이도 추가해놨다.)

 

단계별 풀이

from collections import deque


N = int(input())

dq = deque([i for i in range(1, N+1)])

• 어차피 정수 하나만 주어지므로 재정의 없이 그냥 input()을 사용했다.
• 주어진 N만큼 1부터 순서대로 덱 dq 생성.

while len(dq) > 1:
    dq.popleft()
    dq.append(dq.popleft())

print(*dq)

• dq에 하나만 남을때까지 while문을 반복한다.
• 먼저 제일 위(맨 앞)에 있는 카드를 pop()한다. 왼쪽에서 꺼내야하므로 popleft()를 사용해야한다.
• 그리고 그 다음 카드를 pop()한 뒤 dq의 제일 끝(오른쪽)에 삽입한다.
• 마지막 남은 카드(dq)를 출력한다.

 

전체 코드

내 코드

# 메모리: 55044KB / 시간: 200ms

from collections import deque


N = int(input())

dq = deque([i for i in range(1, N+1)])

while len(dq) > 1:
    dq.popleft()
    dq.append(dq.popleft())

print(*dq)

 

기막힌 숏코딩이다. 규칙을 이용한 풀이!

n,m = int(input()), 1
while m<n: # O(logn)
    m *= 2
print(2*n-m)

• 2 * (N - 2N과 가장 가까운 이전 2의 거듭제곱)
• N이 2의 거듭제곱일 때 (2, 4, 8, 16...), 마지막 남는 카드는 N 자체다.
• 그 외의 경우, 결과는 이전 2의 거듭제곱부터 시작해 2씩 증가.
• N을 2진수로 표현했을 때, 가장 왼쪽 비트를 제외한 나머지를 왼쪽으로 한 칸 시프트하고 맨 오른쪽에 1을 추가한 값과 같다.

---

[11866]요세푸스 문제 0

문제링크: https://www.acmicpc.net/problem/11866

 

종이에 직접 풀어보면 쉬운 문제다.

N명의 사람들이 있다. 1번부터 세서 K번이 되면 제거, 또 1번부터 다시 세서 K번이 되면... 반복이다.

 

단계별 풀이

from collections import deque


N, K = map(int, input().split())

dq = deque([*range(1, N+1)])
ret = []

• N: 사람 수, K: 제거할 순번
• 1부터 N까지의 정수로 이루어진 덱 dq 생성.
• 결과값을 저장할 빈 리스트 ret.

while dq:
    dq.rotate(-K + 1)
    ret.append(dq.popleft())

print(f"<{', '.join(map(str, ret))}>")

• -K + 1만큼 dq를 회전한다.
• 가장 왼쪽에 있는 값을 pop()한 뒤, ret에 추가한다.
• 모든 반복이 끝나면 {값1, 값2, ...}형태로 ret의 모든 요소들을 출력한다.
  • 현재 ret의 요소들은 정수 형태이므로 .join()을 사용하려면 str로 형변환해줘야 함.

rotate()함수를 알고있다면 쉬운 문제다.
참고로 rotate()는 아래와 같이 동작한다.

lst = [1, 2, 3, 4, 5]

1. rotate(3)  
=> [3, 4, 5, 1, 2]  # 시계방향
2. rotate(-3)  
=> [4, 5, 1, 2, 3]  # 반시계방향

 

문제 예시 데이터로 보자면 아래와 같다.
N-1만큼 왼쪽의 원소를 오른쪽 뒤로 이동시킨다고 생각하면 된다.

N, K = 7, 3

1. dq = [(3), 4, 5, 6, 7, 1, 2]
2. dq = [(6), 7, 1, 2, 4, 5]
3. dq = [(2), 4, 5, 7, 1]
4. dq = [(7), 1, 4, 5]
5. dq = [(5), 1, 4]
6. dq = [(1), 4]
7. dq = [(4)]

 

전체 코드

# 메모리: 34008KB / 시간: 60ms

# 반대로 rotate 한 뒤 꺼내주면 된다.
from collections import deque


N, K = map(int, input().split())

dq = deque([*range(1, N+1)])
ret = []

while dq:
    dq.rotate(-K + 1)
    ret.append(dq.popleft())

print(f"<{', '.join(map(str, ret))}>")

---

[28279]덱 2

문제링크: https://www.acmicpc.net/problem/28279

 

큐 2, 스택 2 문제와 마찬가지로 명령어를 순서대로 실행하면 된다.

 

단계별 풀이

from collections import deque
import sys


cmd = iter(sys.stdin.read().split())
next(cmd)

dq = deque()
ret = []

• 모든 입력값을 공백을 기준으로 나눈 뒤, iterator 객체로 변환한다.
• 입력값의 첫번째 값은 명령어의 갯수이므로 next()로 넘겨버린다.
• 빈 덱 dq, 명령어를 저장할 빈 리스트 ret 생성.

for c in cmd:
    if c == "1":
        dq.appendleft(next(cmd))
    elif c == "2":
        dq.append(next(cmd))
    elif c == "3":
        ret.append(dq.popleft() if dq else "-1")
    elif c == "4":
        ret.append(dq.pop() if dq else "-1")
    elif c == "5":
        ret.append(str(len(dq)))
    elif c == "6":
        ret.append("1" if not dq else "0")
    elif c == "7":
        ret.append(dq[0] if dq else "-1")
    else:
        ret.append(dq[-1] if dq else "-1")

sys.stdout.write("\n".join(ret))

• iterator로 변환한 입력값들을 하나씩 순회한다.
• 1과 2는 1(2) 정수값의 형태로 주어지므로, 1(2)의 다음엔 항상 (공백)정수값이 존재한다.
  즉, iterator 속 1(2)의 다음값으로는 항상 정수값이 오는 셈이다. next(cmd) == 정수값
• 모든 순회를 마치면 ret값을 개행문자(\n)로 이어준 뒤 출력한다.

 

전체 코드

# 메모리: 131408KB / 시간: 408ms

from collections import deque
import sys


cmd = iter(sys.stdin.read().split())
next(cmd)

dq = deque()
ret = []

for c in cmd:
    if c == "1":
        dq.appendleft(next(cmd))
    elif c == "2":
        dq.append(next(cmd))
    elif c == "3":
        ret.append(dq.popleft() if dq else "-1")
    elif c == "4":
        ret.append(dq.pop() if dq else "-1")
    elif c == "5":
        ret.append(str(len(dq)))
    elif c == "6":
        ret.append("1" if not dq else "0")
    elif c == "7":
        ret.append(dq[0] if dq else "-1")
    else:
        ret.append(dq[-1] if dq else "-1")

sys.stdout.write("\n".join(ret))

---

[2346]풍선 터뜨리기

문제링크: https://www.acmicpc.net/problem/2346

 

풍선 안에 있는 번호대로 이동한 뒤 터뜨린다.
양수면 오른쪽, 음수면 왼쪽으로 번호만큼 이동한다.

 

풀면서 조금 헷갈렸던 문제다.

 

단계별 풀이

from collections import deque
import sys


cmd = iter(sys.stdin.read().split())
next(cmd)

dq = deque(enumerate(map(int, cmd), start=1))
ret = []

• 명령어를 공백을 기준으로 나눈 뒤 iterator화 시키고, 풍선의 갯수를 나타내는 첫번째 요소를 next()로 넘겨준다.
• 풍선의 순서를 출력해야하므로 (순서, 풍선 속 번호)로 dq에 저장.
• 결과값을 저장할 빈 리스트 ret 생성.

while dq:
    idx, move = dq.popleft()
    ret.append(idx)

    if move > 0:
        dq.rotate(-(move - 1))
    else:
        dq.rotate(-move)

print(*ret)

• dq가 빌 때까지 while문을 반복한다.
• 맨 왼쪽의 풍선을 pop()으로 꺼낸뒤 idx(순서), move(풍선 속 번호)로 할당한다.
• idx(순서)는 ret에 추가한다.
  • 만약 번호가 양수라면, -(번호-1)값만큼 rotate시킨다. (번호-1)만큼 왼쪽으로 돌리는 셈이다.
  • 음수라면 -(번호)만큼 rotate시킨다. 음수니까 결국은 (번호)만큼 오른쪽으로 돌리는것과 같다.

풍선 = [1, 2, 3, 4, 5]  
1번풍선에는 3, 또는 -3이 있다고 가정해보자.  
3이라면 4, -3이라면 3이 선택되어야 한다.

1. pop()으로 1 제거  
=> [2, 3, 4, 5]

2.1 풍선 속 번호가 3이라면 => rotate(-2)  
[4, 5, 2, 3]  
2.2 풍선 속 번호가 -3이라면 => rotate(3)  
[3, 4, 5, 2]

• 먼저 pop()을 실행한 뒤 조건을 체크한다.
  • 양수일땐 제거된 현재 위치값을 보정해야 하기 때문에 -1,
  • 음수일땐 따로 보정할 필요가 없으므로 그대로 사용 가능.

 

전체 코드

# 메모리: 34016KB / 시간: 64ms

from collections import deque
import sys


cmd = iter(sys.stdin.read().split())
next(cmd)

dq = deque(enumerate(map(int, cmd), start=1))
ret = []

while dq:
    idx, move = dq.popleft()
    ret.append(idx)

    if move > 0:
        dq.rotate(-(move - 1))
    else:
        dq.rotate(-move)

print(*ret)

---

[24511]queuestack

문제링크: https://www.acmicpc.net/problem/24511

 

스택은 LIFO, 큐는 FIFO다.
pop()을 할 때에 스택은 뒤에서, 큐는 앞에서 해야한다.

무작정 '아~ 팝 하라고? ㅇㅋ. .pop()' 하면 안된다.
여기서 말하는 팝은 함수 pop()이 아닌 "꺼낸다"는 의미의 "pop"이다.

 

(원리만 이용한 풀이는 전체 코드 항목에 추가해뒀다.)

 

단계별 풀이

from collections import deque
from sys import stdin


input = stdin.readline

N = int(input())

• input 재정의 후 자료구조의 갯수 N 할당.

qs = zip(map(int, input().split()), map(int, input().split()))
dq = deque([element for i, element in qs if not i])

_ = input()
ret = []

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

• zip()을 이용해 (스택/큐 구분값, 존재할 정수값)으로 묶는다.
• 구분값이 1일때는 스택, 0일때는 큐 이므로 구분값이 0인 경우에만 정수값을 dq에 할당한다.
  • 스택은 append한 값 == pop한 값 이므로 큐인 경우만 계산해주면 된다.
• 주어지는 정수의 개수는 _로 넘겨버리고, 결과값을 저장할 빈 리스트 ret을 생성한다.
• 주어진 정수들은 int로 변환 후 리스트 new_elements로 만들어준다.

for n in new_elements:
    dq.appendleft(n)
    ret.append(dq.pop())

print(*ret)

• new_elements를 하나씩 순회한다.
• dq의 왼쪽에 n을 추가한뒤, 오른쪽에서 pop()한 값을 ret에 저장한다.

 

전체 코드

# 메모리: 53788KB / 시간: 160ms

from collections import deque
from sys import stdin


input = stdin.readline

N = int(input())

qs = zip(map(int, input().split()), map(int, input().split()))
dq = deque([element for i, element in qs if not i])

_ = input()
ret = []

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

for n in new_elements:
    dq.appendleft(n)
    ret.append(dq.pop())

print(*ret)

 

아래는 원리만 이용한 버전이다.

from collections import deque
from sys import stdin


input = stdin.readline

input()

# 큐에 해당하는 요소만 선택하여 역순으로 저장
a = [y for x, y in zip(input().split(), input().split()) if x == "0"][::-1]

m = int(input())
a.extend(input().split())  # 여러번 append하지 않아도 됨.

# m개의 요소만 출력
print(*a[:m])

• 어차피 최종 리턴값들만 출력하면 되므로, 큐에 해당하는 요소만 처음부터 역순으로 저장한다.
• 그리고 주어지는 정수값들을 오른쪽에 추가한다. (extend()를 사용하여 한번에 추가.)
• 마지막으로 처음부터 m-1까지의 요소들만 출력한다.
  • a = [4, 1, 2, 4, 7]인 상태에서 a[:m]