acmicpc.net 11723(비트마스크)

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

문제를 풀긴 풀었는데 파이썬이라 시간초과가 떠버린다. 파이썬으로 푼 사람이 없으면 못푸는 

문제겠거니 하고 그냥 넘어가겠는데 푼사람이 한명 있어서.... 삽질을 엄청 해봤는데 시간초과를 

극복할 방법이 안보인다.

비트마스크를 이용해서 빨리빨리 처리할수 있는것중 하나가 집합이랜다. 비트의 성질을 이용하는건데..

1~5까지 저장하는 집합을 만든다고 하면 이진수 00000 이 있다고 가정하고, 맨 왼쪽부터 5,4,3,2,1

로 치고, 1이면 5라는 원소가 집합에 있고, 0이면 원소가 없다고 가정하며 프로그래밍하는

방식이다. 

소스 1.

set = 0
for i in xrange(int(raw_input())):
    com = raw_input() #입력받아서
    if com[:2]=='ad': #add다 싶으면
        set |= 1<<int(com[4:]) #set에 넣음.ex) 2를 넣었다싶으면 set = set | (1<<2)가 되므로 set == 이진수 100이 된다. 3을 넣으면 set |= 1<<3인데 1<<3은 1000이므로 앞의 2까지 추가해서 이진수 1100이 된다. 
                                             #맨 오른쪽 0은 안쓰는 영이고, 그 이후로 왼쪽으로 가면서 1,2,3,을 처리하는거라 보면 됨.
    elif com[0]=='r': #remove다 싶으면
        set &= ~(1<<int(com[7:])) #위처럼 해당 비트를 ~를 이용해서 0으로 만들어 준다. 그 이후 &연산을 하게되면 우리가 만들어준 부분이 0이므로 이것과 충돌해서 0이 되게 된다.
    elif com[0]=='c': #check가 싶으면 해당 비트만 출력한다. 
        num = com[6:]
        print (set & (1<<int(num)))>>int(num)
    elif com[0]=='t': #toggle은 대표적으로 xor을 이용하므로 이걸 이용한다.
        set ^= 1<<int(com[7:])
    elif com[:2]=='al': #다 1로 세팅해주려면 그냥 아래처럼 설정해주면 된다. 맨앞의 0b는 파이썬에서 2진수라는 표시이다. 
        set = 0b1111111111111111111110
    elif com[0]=='e': #0이면 0으로 세팅
        set = 0

시간초과가 걸려서 개선해본 소스 2.

http://qkqhxla1.tistory.com/637 에서 딕셔너리는 해쉬 테이블이라서 메모리를 먹는대신 검색이 

빠르다는걸 이용하면 될거같아서 만들어본거...

set = 0
case = {'d':lambda s,c:s|(1<<int(c)),'e':lambda s,c:s&(~(1<<int(c))),'h':lambda s,c:(s&(1<<int(c)))>>int(c),'o':lambda s,c:s^(1<<int(c)),'l':0b1111111111111111111110,'m':0}
#사전에다가 미리 저장해놓고 람다로 계산하면 더 빠를줄알았는데 아니다. 

for i in xrange(int(raw_input())):
    com = raw_input()
    if com[1]=='h':
        print case[com[1]](set,com.split()[1])
    elif com[1]=='d' or com[1]=='e' or com[1]=='o':
        set = case[com[1]](set,com.split()[1])
    else:
        set = case[com[1]]

이거말고 몇개 더 해봤는데 다 시간초과 떠서 포기....... 이거 똑같이 c로 짜면 통과한다..