15787 기차가 어둠을 헤치고 파이썬

15787번_기차가 어둠을 헤치고 은하수를.py

deque or 비트마스킹N개의 기차기차는 20개의 좌석명령 1. 1 i x : i번째 기차, x 좌석에 사람을 태워라명령 2. 2 i x : i번째 기차, x 좌석에 앉은 사람은 하차명령 3. 3 i : i번째 기차에 앉은 모든 승객 뒤

velog.io

처음 풀이로는

명령에 따라 배치도를 수정하는 함수와 같은 배치도인지 대조하는 2개의 함수를 썼었다.

그러나 시간초과가 떴는데,

시간제한이 1초고, n이 10만이라 n^2만 되도 시간초과가 나버렸다.

그래서 다른 풀이를 봤는데, deque로 푸는 방식이 인상적이었다.

1. 일단 deque의 rotate를 활용해서 이동을 구현한 방식이 좋았다.

2. 공백으로 이루어진 명령을 하나의 변수에 리스트로 넣어서

인덱스로 접근해서 명령하나마다 풀어나가는 방식이 배울만했다. 나는 아예 명령어 배열을 따로 만들어서 했는데

그럴필요가 없었다.

3. 중복확인을 not in 으로 처리한게 가장 포인트였다. 나는 이부분에서 이중for문을 써서 실패했는데, for문 1개로도 가능했다.

from collections import deque

import sys

input=sys.stdin.readline

n,m=map(int,input().split())

train=[ deque([0]*20) for _ in range(n)] # deque로 만들기

for i in range(m):

op=list(map(int,input().split()))

if op[0]==1:

train[op[1]-1][op[2]-1]=1

elif op[0] == 2:

train[op[1] - 1][op[2] - 1] = 0

elif op[0] == 3:

train[op[1] - 1].rotate(1) #오른쪽으로 1씩 이동하고 0번째 제거

train[op[1]-1][0]=0

else:

train[op[1] - 1].rotate(-1) # 왼쪽으로 1씩 이동하고 마지막좌석 제거

train[op[1] - 1][19] = 0

answer=[]

for i in train:

if i not in answer: # 중복이 안되는 열차 배치도만 고르는 로직

answer.append(i)

print(len(answer))

Keep Going Dev