문제자체는 쉽지만 저 아주 빡도는 메모리 제한을 보라!! 무려 꼴랑 4MB!!
~해서 비트마스크로 풀어야하는데 처음이라 뭔지 모르겠어서 우왕좌왕하다가 정리해본다.
N비트 정수 = N개의 원소를 갖는 집합
하나의 bit = 하나의 원소
1 = 집합에 포함되어 있다
0 = 집합에 포함되어있지 않다
💡 N개의 원소를 가지는 집합을 표현할때, N개의 boolean 원소를 갖는 배열을 선언하는 것이 아니라, N비트 정수 1개로 표현하는 것이 중요한 포인트!!
💡 문제에서 메모리 제한이 4MB인것도 정수형 변수의 메모리가 4MB라서 인거임
💡 32비트(or 64비트)가 넘어가면 오버플로우 발생하니 조심!
S = 0
S = (1 << N) - 1
ex) 6비트 정수로 꽉 찬 집합을 만들려면?
S = S | (1 << K)
ex) S = 100000(2)
일때 3
을 추가하고 싶다면?
S = S & ~(1 << K)
ex) S = 101000(2)
일때 3
을 삭제하고 싶다면?
S = S ^ (1 << K)
ex) S = 101000(2)
일때 3
을 토글하고 싶다면?
if S & (1 << K):
포함 O
else:
포함 X
ex1) S = 101000(2)
일때 3
이 포함되어있는지 확인하려면?
ex2) S = 100000(2)
일때 3
이 포함되어있는지 확인하려면?