[Python] 백준 #18115 - 카드 놓기[try_again]

문제

---

 

18115번: 카드 놓기

코드

---

My answer(시간초과)

import sys
input=sys.stdin.readline

ocnt=0
n=int(input())
origin=[0 for i in range(n)]
card=[i for i in range(n,0,-1)]
tech=list(map(int,input().split()))

for i in range(len(tech)):
    if(tech[i]==1):
        for j in range(n):
            if(origin[j]==0):
                break
        origin[j]=card[i]
    if(tech[i]==2):
        origin[ocnt+1]=card[i]
        ocnt+=1
    if(tech[i]==3):
        for j in range(len(origin)-1,-1,-1):
            if(origin[j]==0):
                break
        origin[j]=card[i]
print(*origin)

Another answer

from collections import deque

N = int(input())
tech = deque(map(int, input().split()))
card = deque(range(1, N+1))
origin = deque()
while tech:
    t = tech.pop()
    a = card.popleft()
    if t == 1:
        origin.appendleft(a)
    elif t == 2:
        origin.insert(1, a)
    elif t == 3:
        origin.append(a)
print(*origin)

풀이

---

내 코드는 시간초과가 떴다. 나는 그냥 리스트와 인덱스를 이용해서 카드를 재배치했는데, 우선 1~n까지의 카드를 역순으로 정렬해놓고 ocnt라는 현재 카드의 맨위를 나타내는 변수를 선언하고, 1번기술을 사용할 때는 origin(우리가 구하려는 원래카드배열)의 첫번째부터 0인 값이 나오면(맨처음에 전부0으로 초기화해둠) 그 위치에 카드를 넣는다. 다음으로 2번기술을 사용하면 ocnt+1위치에 카드를 넣고 3번기술은 origin의 마지막부터 0이나오면 추가하는 방식을 썼다. 답은 제대로 나왔는데 맨위와 맨밑을 찾을 떄 반복문을 계속 사용해서 시간초과가 뜨는 것 같다. 나도 스택이나 큐를 쓰는 방법을 생각해봤었는데, 맨위와 맨뒤는 큐를 사용하면 쉬울 것 같긴했는데 2번쨰기술을 사용할땐 맨위에서 두번째에 카드를 넣는것을 어떻게 구현할 지 몰랐다. 다른사람의 코드를 참고해보니 insert함수를 이용하여 원하는 위치에 카드를 넣었다. deque를 통해 양방향큐를 구현하고 맨뒤와 맨앞은 appendleft와 append를 써서 삽입하고 위에서 두번쨰는 insert를 ㅣ용해서 인덱스1위치에 넣어줬다.