[백준 18115번] 카드 놓기

📖문제:

 

📙풀이:

초기 코드에서 일정 규칙에 따라 숫자 카드가 쌓이는데, 문제에서 초기 코드를 알아내야 하기 때문에 거꾸로 생각하는 부분이 어려웠다.

하지만 막상 방법을 알고 나니 정말 간단했다. 쌓여 있는 숫자 카드는 항상 위에서부터 1, 2, 3, 4, 5.. 순으로 같고, 1은 결국 마지막 규칙에 의해 쌓인 것이고, 2는 마지막 - 1 번째 규칙에 의해 쌓인 것이기 때문에 규칙의 순서를 뒤집어서 생각하면 된다.

그리고 시간 복잡도를 줄이기 위해 덱을 사용했다.

덱은 양쪽 끝에서 삽입과 삭제가 가능하고, 그 때 시간 복잡도가 O(1)로 매우 빨라 이러한 문제에 유리할 것 같다.

 

✏️코드:

'''
https://www.acmicpc.net/problem/18115
문제: 카드 놓기
난이도: 실버3
'''

import sys
from collections import deque

# 이미 쌓여 있는 숫자 카드들(1, 2, 3... 순서)의 초기 상태를 역추적해야 하므로,
# skill의 순서도 거꾸로 생각해야 함!
# 예를 들어, 1은 맨 마지막에 skill로 인해 젤 위에 쌓임
N = int(sys.stdin.readline())
skill = list(map(int, sys.stdin.readline().split()))
skill.reverse()

dq = deque()
for i in range(N):
    if skill[i] == 1:
        dq.appendleft(i + 1)
    elif skill[i] == 2:
        dq.insert(1, i + 1)
    elif skill[i] == 3:
        dq.append(i + 1)

for i in dq:
    print(i, end=" ")

 

🔗링크:

https://www.acmicpc.net/problem/18115