Problem

Solution

1) Count 방식

$2^k$ 개에 해당하는 binary code를 모두 얻어야 된다. $2^k$ 내에 있는 binary code를 count하고 count를 하나씩 지워나가는 식으로 체크한다. count를 지워나가는 도중 count가 0으로 떨어지지 않으면 False를 return 한다.

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        need = 1 << k # bit shift, bit shift를 통해 2^k 승에 해당하는 10진수 값을 찾는다.
        got = set()
        
        for i in range(k, len(s) + 1):
            tmp = s[i - k:i] # s에서 k개 binary code씩 순차적으로 자른다.
            # 해당 binary code가 got에 있으면 count를 하나씩 빼나간다.
            if tmp not in got:
                got.add(tmp)
                need -= 1
                # 모든 count가 다 소진되면 True return
                if need == 0:
                    return True
                # 이미 해당 binary code가 got에 있다면 다음 반복 진행
        return False # count가 다 소진되지 않으면 False return

2) Total 요소 갯수를 비교하는 방식

got에 k개씩 자른 substring이 들어가는 부분까지는 동일하지만 count를 소진하는 방식이 아닌 total 요소 갯수를 비교하는 방식

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        got = {s[i - k:i] for i in range(k, len(s) + 1)} # 1)과 동일
        return len(got) == 1 << k # got에 있는 binary code 갯수가 2^k 갯수와 동일한지 체크하여 boolean return

3) Deque()를 이용한 방법 (비추!)

string을 character 하나하나씩 비교하는 방법으로 character가 k개 찼을 때마다 set()에 요소를 추가하고, Deque()에서는 요소를 꺼내는 방법
$O(n)$을 줄이기 위해 list() 대신 Deque()를 사용한 것 같지만 결국 set()과 list()를 쓰는 꼴로 보인다.
또한 python의 속도가 빠른 slicing 기능을 사용하지 않고 character 하나하나 순차적으로 iterate한다. 그래서 속도가 1), 2)에 비해 현저히 느리다.

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        seen = set()
        q = deque()
        for c in s:
            q.append(c)
            # Deque()에 요소가 k개 만큼 차면 seen에는 요소 추가 Deque()에서는 삭제
            if len(q) == k:
                seen.add(''.join(q))
                q.popleft()
        return len(seen) == 1 << k