18115번: 카드 놓기
수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다.
www.acmicpc.net
문제
수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.
- 제일 위의 카드 1장을 바닥에 내려놓는다.
- 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
- 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!
놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.
입력
첫 번째 줄에는 N (1 ≤ N ≤ $10^6$)이 주어진다.
두 번째 줄에는 길이가 N인 수열 A가 주어진다. $A_i$가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. $A_i$는 1, 2, 3 중 하나이며,$A_n$은 항상 1이다.
출력
초기 카드의 상태를 위에서부터 순서대로 출력하여라.
코드
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
cards = list(map(int, input().split()))
ans = deque()
for i in range(n):
if cards[n-1-i] == 1: # 제일 위의 카드 1장 내려놓음
ans.appendleft(i+1)
elif cards[n-1-i] == 2: # 위에서 두번째 카드 내려놓음(카드 2장 이상일 때 사용 가능)
tmp = ans.popleft()
ans.appendleft(i+1)
ans.appendleft(tmp)
else: # 제일 밑의 카드 내려놓음(카드 2장 이상일 때 사용 가능)
ans.append(i+1)
print(*ans)
놓여진 카드는 0번 인덱스부터 N-1번 인덱스까지 1, 2, 3, ..., N 순서이다.
카드는 밑에서부터 쌓인 것이므로 가장 아래 카드인 N이 가장 먼저 내려놓아진 카드라는 뜻이다. 그렇기 때문에 숫자 i 카드는 n+1-i번째로 내려놓아진 카드라는 뜻이다. 코드에서는 cards의 인덱스 범위가 0~N-1이므로 n-1-i번째라고 보면 된다.
1번 카드부터 기술을 거꾸로 쓴다고 생각하여 원래의 위치를 찾아주면 된다
'문제풀이 > 자료구조' 카테고리의 다른 글
[Python/파이썬] 백준 5397번 키로거 (0) | 2024.01.14 |
---|---|
[Python/파이썬] 백준 3986번 좋은 단어 (1) | 2023.12.18 |
[Python/파이썬] 백준 22866번 탑 보기 (0) | 2023.11.21 |
[Python/파이썬] 백준 5875번 오타 (0) | 2023.10.27 |
[Python/파이썬] 백준 1655번 가운데를 말해요 (0) | 2023.10.08 |