deque or 비트마스킹
N개의 기차
기차는 20개의 좌석
명령 1.
1 i x : i번째 기차, x 좌석에 사람을 태워라
명령 2.
2 i x : i번째 기차, x 좌석에 앉은 사람은 하차
명령 3.
3 i : i번째 기차에 앉은 모든 승객 뒤로 한칸. 20번 좌석 사람은 하차
명령 4.
4 i : i번째 기차 모두 앞으로 한칸. 1번 좌석은 하차
기차가 지나갈 때 승객이 앉은 상태를 목록에 기록하며
이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널수 없다.
기록이 존재하기 때문에 set으로 check해서 은하수를 건널 수 있는지 check
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
trains = [set([]) for _ in range(n)]
for _ in range(m):
op = list(map(int, input().split()))
if op[0] == 1:
trains[op[1]-1].add(op[2])
if op[0] == 2:
trains[op[1] - 1].discard(op[2])
if op[0] == 3:
tr = list(trains[op[1] - 1])
temp = set()
for t in tr:
if t + 1 > 20:
continue
temp.add(t+1)
trains[op[1] - 1] = temp
if op[0] == 4:
tr = list(trains[op[1] - 1])
temp = set()
for t in tr:
if t - 1 < 1 :
continue
temp.add(t - 1)
trains[op[1] - 1] = temp
answer = set()
for train in trains:
t = tuple(sorted(train))
answer.add(t)
print(len(answer))
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
train = [0]*n
print(bin(1 << 20))
print(bin(2**20))
# 이때 오른쪽부터 자리 배치를 하여 3210 순으로 배치가 됨.
for _ in range(m):
op = list(map(int, input().split()))
if op[0] == 1:
i, x = op[1] - 1, op[2] - 1
train[i] = train[i] | 1 << x # '|' : bit 단위로 or연산
# << (Binary left Shift) : bit 단위로 왼쪽으로 비트단위 밀기 연산을 합니다. ('|' 보다 연산자 우선순위가 높음.)
# n << m : n * 2의 m승
# 즉 2진수에 맞게 x 자리에 1이되고 나머지는 0.
elif op[0] == 2:
i, x = op[1] - 1, op[2] - 1
train[i] = train[i] & ~(1 << x)
# ~ : 비트 NOT 연산
# ~(1 << x) 을 통해서 x자리만 0이 되고 나머지는 1
# 이를 통해서 train[i]는 유지하되 x자리는 AND 연산자로 0이 되어 하차
elif op[0] == 3:
i = op[1] - 1
train[i] = train[i] << 1
train[i] = train[i] & ~(1 << 20)
# train[i] << 1 을 통해서 왼쪽으로 비트단위 밀기 연산
# 0011 -> 0110
# 1000 -> ~(1000) -> 0111 : AND 연산을 하여 맨 앞자리를 비워준다.
elif op[0] == 4:
i = op[1] - 1
train[i] = train[i] >> 1
# train[i] >> 1 을 통해서 오른쪽으로 비트단위 밀기 연산
# 0100 -> 0010
print(len(set(train)))
rotate(n) 함수 : deque에서 사용할 수 있는 함수로 n 만큼 deque가 이동한다. 예를들어, n = 1 일 경우, [-1]에 있던 값은 [0] 으로 rotate한다.
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int,input().split())
train = [deque([0]*20) for _ in range(n)]
for _ in range(m):
box=list(map(int,input().split()))
if box[0]==1:
train[box[1]-1][box[2]-1]=1
elif box[0]==2:
train[box[1]-1][box[2]-1]=0
elif box[0]==3:
train[box[1]-1].rotate(1)
train[box[1]-1][0]=0
else:
train[box[1]-1].rotate(-1)
train[box[1]-1][19]=0
answer=[]
for i in train:
if i not in answer:
answer.append(i)
print(len(answer))