2024.10.5 백준(Python) 18115 카드놓기

카드 놓기 

 

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초 (추가 시간 없음)	1024 MB	5619	3099	2394	54.261%

문제

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

입력

첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. Ai가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

출력

초기 카드의 상태를 위에서부터 순서대로 출력하여라.

예제 입력 1 

5
1 1 1 1 1

예제 출력 1 

5 4 3 2 1

예제 입력 2 

5
2 3 3 2 1

예제 출력 2 

1 5 2 3 4

 

 

정답 코드

from collections import deque

N = int(input())  # N: 카드의 개수 입력받기
deq = deque()  # 최종적으로 처음 카드의 배치를 담을 덱 생성
result_dq = deque(range(1, N + 1))  # 1부터 N까지의 숫자가 담긴 덱 (처음에는 1~N 카드가 이 순서로 있다고 가정)

skill = list(input().split())  # 수현이가 사용한 기술들 (1, 2, 3으로 이루어진 문자열)을 입력받음

# 기술을 역순으로 처리하여 처음 카드를 복원하기
for i in reversed(skill):
    a = result_dq.popleft()  # 맨 앞의 카드 하나를 꺼냄 (1부터 N까지 순차적으로 사용됨)
    
    if i == '1':  # 1번 기술: 맨 위 카드를 내려놓는 기술
        deq.appendleft(a)  # 꺼낸 카드를 deq의 맨 앞에 추가
    elif i == '2':  # 2번 기술: 두 번째 카드를 내려놓는 기술
        deq.insert(1, a)  # 꺼낸 카드를 deq의 두 번째 위치에 추가
    else:  # 3번 기술: 맨 아래 카드를 내려놓는 기술
        deq.append(a)  # 꺼낸 카드를 deq의 맨 뒤에 추가

print(*deq)  # 복원된 카드 순서를 출력 (deq에 담긴 값을 띄어쓰기 없이 출력)

 

삭제한 순서와 반대로 카드를 추가해주기만 하면 되는 문제