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

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

[문제 풀이]

1. set을 이용한 풀이

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))

2. 비트 마스킹 풀이

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)))

3. deque를 이용한 풀이

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))