[백준] 15787번번번 (python 파이썬)

https://www.acmicpc.net/problem/15787

 

구현문제이다. 

 

처음 구현한 방법은

2차원 배열을 사용하여 해당명령을 수행하고

명령을 다 수행했으면

2차원 배열들을 문자열로 바꿔 ( ex: [[1, 0, 0, 1], [0, 1, 1, 0]] -> [ '1001, '0110' ] ) 모든 기차들을 다 비교하였다.

-> 시간초과

 

두번째 방법은

비트 연산을 사용하여 명령을 수행하였고

visited[False] 배열을 사용하여 중복 값을 체크하였다.

 

import sys

input = sys.stdin.readline
n, m = map(int, input().split(' '))
trains = [0] * (n + 1)
commands = [list(map(int, input().split(' '))) for _ in range(m)]
visited = [False] * (2 ** 22)


def conduct(trains):
    for i in range(m):
        if commands[i][0] == 1:
            train_n = commands[i][1]
            seat = commands[i][2] - 1
            trains[train_n] = trains[train_n] | (1 << seat)
        elif commands[i][0] == 2:
            train_n = commands[i][1]
            seat = commands[i][2] - 1
            trains[train_n] = trains[train_n] & ~(1 << seat)
        elif commands[i][0] == 3:
            train_n = commands[i][1]
            trains[train_n] = trains[train_n] << 1
            trains[train_n] = trains[train_n] & ~(2 ** 20)
        elif commands[i][0] == 4:
            train_n = commands[i][1]
            trains[train_n] = trains[train_n] >> 1


def vailTrain():
    count = 0

    for i in range(1, n + 1):
        if not visited[trains[i]]:
            count += 1
            visited[trains[i]] = True

    return count


conduct(trains)
print(vailTrain())