https://www.acmicpc.net/problem/18115
공부 날짜 : 2023.01.20, 2023.01.24
정답 참조 여부 : X
카드를 명령에 따라 순서대로 내려 놓았을때 결과가 1~n까지 순서대로 놓여있을 때 처음 카드뭉치의 순서를 구하는 문제이다.
어렵진 않았다.
처음에 구현할때는 두번째 카드를 내려놓는 명령을 위해 첫번째 카드를 구분하고, 명령의 순서대로 1~n 까지의 카드를 순서대로 내려놓았다. 내려놓아진 결과를 바탕으로 처음 카드뭉치를 복원하는 식으로 구현했다.
결과는 시간초과 솔직히 이때 멘탈이 흔들렸다. 자료구조도 deck구조로 맞게 사용했고, 문제에서 주어진대로 순차적으로 진행했기 때문에 시간초과면 전혀 다른 로직으로 구현해야 했다.
결국 문제를 잡은 당일에 못풀었다가, 설 연휴를 보내고나서 다시 풀었다.
다시 푼 방법자체는 비슷했다. 첫번째 카드를 구분하고 나머지 덱에서 카드를 넣어주는데
순서대로 카드를 내려놓고 결과를 복원하는게 아닌 명령을 역순으로 내려진 카드를 덱에 집어넣는 식으로 구현했더니 정답으로 나왔다.
너무 구현문제만 풀다보니 순서대로 문제를 푸는게 익숙했던거 같다. 초기상태 복원을 위해 역순으로 진행할 수 있다는 점을 배울 수 있었던 문제였다.
소스코드
from collections import deque
import sys
input = sys.stdin.readline
#################################################
n = int(input())
# 수현이가 수행한 동작을 담아둔 변수(길이 n)
input_data = list(map(int, input().split()))
# 결과가 저장될 변수, 첫번째 카드는 따로 저장
answer_deck = deque()
frist_card = 1
# 바닥에 놓인 카드중 맨 위의 카드
now_card = 2
#명령의 역순으로 카드를 집어넣기
for index in range(n-2, -1, -1):
order = input_data[index]
if order == 1:
answer_deck.appendleft(frist_card)
frist_card = now_card
elif order == 2:
answer_deck.appendleft(now_card)
elif order == 3:
answer_deck.append(now_card)
now_card += 1
print(frist_card, end = " ")
for num in answer_deck:
print(num, end = " ")
