[백준 15787번] 파이썬 - 기차가 어둠을 헤치고 은하수를

백준 15787 - 기차가 어둠을 헤치고 은하수를

시간 제한 1초, 메모리 제한 512MB

# 조건

• N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다.
• 기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다.
• 기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다.
• 명령의 종류는 4가지로 다음과 같다.
  • 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
  • 2 i x : i번째 기차에 x번째 좌석에 앉은 사람은 하차한다. 만약 아무도 그자리에 앉아있지 않았다면, 아무런 행동을 하지 않는다.
  • 3 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 뒤로간다. k번째 앉은 사람은 k+1번째로 이동하여 앉는다. 만약 20번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
  • 4 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 앞으로간다. k번째 앉은 사람은 k-1 번째 자리로 이동하여 앉는다. 만약 1번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
• M번의 명령 후에 1번째 기차부터 순서대로 한 기차씩 은하수를 건너는데 조건이 있다.
• 기차는 순서대로 지나가며 기차가 지나갈 때 승객이 앉은 상태를 목록에 기록하며 이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널 수 없다.
• 예를 들면, 다음 그림을 예로 들었을 때, 1번째 기차와 같이 승객이 앉은 상태는 기록되지 않았기 때문에 은하수를 건널 수있다.
• 2번째 기차와 같은 상태도 기록되지 않았기 때문에 2번째 기차도 은하수를 건널 수 있다.
• 3번째 기차는 1번째 기차와 승객이 앉은 상태가 같으므로 은하수를 건널 수 없다.

• 처음에 주어지는 기차에는 아무도 사람이 타지 않는다.
• 은하수를 건널 수 있는 기차의 수를 출력하시오.

입력

• 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다.
• 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다.

출력

• 은하수를 건널 수 있는 기차의 수를 출력하시오

# 접근 방법

• 리스트와 SET을 이용해서도 풀 수 있지만 비트마스킹으로 풀어보았다.
• 주어지는 명령어는 아래 비트 연산을 통해서 해결해주었다.
  • | 1<<x 를 통하여 왼쪽으로 밀어주고
  • & ~(1<<x) 를 통해서 x자리만 0이되고 나머지는 1
  • train[i] << 1 을 통해서 밀어주고 마찬가지로 & ~(1<<20)을 통해서 맨앞자리 비워주기
  • train[i] >> 1 을 통해서 밀어준다.
    • 자동으로 1번자리 사람은 하차하게 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def q1(num, seat):  
    # seat자리 채워주기  
    # or 연산이므로 자리에 타있으면 그대로 1    
    train[num] |= 1 << seat  

def q2(num, seat):  
    # & ~ 통해 자리에 타잇는 사람 하차시키기  
    # ~ (not)을 하므로 자리에 타잇다면 1 & 0 의 연산을 하는 것것    
    train[num] &= ~(1 << seat)  

def q3(num):  
    # 한칸 씩 뒤로밀기  
    # 이후 2번 명령어와 같이 20번째자리 하차    
    train[num] <<=  1  
    train[num] &=  ~(1<<20)  

def q4(num):  
    # 한칸 앞으로 밀기  
    # 1번자리는 자동 하차    
    train[num] >>= 1  


N, M = map(int, input().split())  
train = [0] * (N+1)  

for _ in range(M):  
    query = [*map(int, input().split())]  
    if query[0] == 1:  
        q1(query[1], query[2]-1)  
    elif query[0] == 2:  
        q2(query[1], query[2]-1)  
    elif query[0] == 3:  
        q3(query[1])  
    else:  
        q4(query[1])  

result = set()  
for i in range(1, N+1):  
    result.add(train[i])  
print(len(result))