Link: https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/
I. 문제 정의
Binary String인 s와 정수 k가 주어진다.
k길이 만큼의 모든 binary code 조합의 리스트(ex: [‘00’, ‘10’, ‘01’, ‘11’] when k = 2)의 모든 원소가 s의 substring으로 존재하는지를 체크하는 문제이다.
II. 내 맘대로 풀이
s의 길이의 최대치는 500,000로 시간복잡도가 O(n)이 아니면 시간초과가 날 것이 뻔하지만 문제를 보자마자 해보고 싶었던 풀이가 있어서 속행
1, 우선 k를 넣어주면 그 길이 만큼의 모든 binary string가 담긴 set이 반환되는 함수를 정의한다.
1
2
3
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
bin_set = self.get_bin_list(k) # 1
2, 포인터 두 개 head, tail을 두고 이 tail을 s의 끝까지 이동시킨다.
1
2
3
4
5
6
7
8
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
bin_set = self.get_bin_list(k)
head, tail = 0, k
while tail <= len(s): # 2
head += 1
tail += 1
3, head와 tail로 s를 슬라이싱하면 딱 k 길이만큼의 substring이 완성되는데 bin_set에서 이 substring이 있으면 제거해준다.
1
2
3
4
5
6
7
8
9
10
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
bin_set = self.get_bin_list(k)
head, tail = 0, k
while tail <= len(s):
if s[head:tail] in bin_set:
bin_set.remove(s[head:tail]) # 3
head += 1
tail += 1
4, 만약 bin_set이 비게 되면 모든 binary string을 체크한 것이므로 True를 반환하고 종료. while문이 끝날 때까지 bin_set에 체크되지 않은 binary string이 있다면 False를 반환
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
bin_set = self.get_bin_set(k)
head, tail = 0, k
while tail <= len(s):
if s[head:tail] in bin_set:
bin_set.remove(s[head:tail])
if not bin_set: # 4
return True
head += 1
tail += 1
return False
일단 hasAllCodes()의 while문 부분만 봐서는 최악의 경우엔 O(n)으로 동작하고 k의 길이가 길어질수록 이 시간은 줄어든다.
그럼 get_bin_set()을 구현해본다.
5, result set을 준비하고 이 result를 채워줄 helper 함수를 정의한다. 이 함수에는 result와, result를 채울 때 쓸 배열 하나와 조합할 숫자 1과 0을 담은 string(리스트라도 상관없음), 그리고 k를 넣어준다.
1
2
3
4
5
class Solution:
def get_bin_set(self, k):
result = set()
self.helper(result, [], '10', k) # 5
return result
6, 백트래킹으로 result를 채울 helper를 구현한다. 우선 base condition은 arr.length가 k일 때이고, 이 때 arr에 담긴 binary string들을 하나의 string으로 합쳐 result에 추가한다.
1
2
3
4
5
class Solution:
def helper(self, result, arr, iterable, k):
if len(arr) == k: # 6
result.add(''.join([_ for _ in arr]))
return
7, iterable(0과 1이 담긴 string)을 순회하면서 하나씩 arr에 담고 재귀호출한다. 재귀호출이 끝났을 때 해당 숫자를 제거해준다.
1
2
3
4
5
6
7
8
9
10
class Solution:
def helper(self, result, arr, iterable, k):
if len(arr) == k:
result.add(''.join([_ for _ in arr]))
return
for i, item in enumerate(iterable): # 7
arr.append(iterable[i])
self.helper(result, arr, iterable, k)
arr.pop()
전체코드는 아래와 같지만 당연하게도 시간초과가 난다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
def helper(self, result, arr, iterable, k):
if len(arr) == k:
result.add(''.join([_ for _ in arr]))
return
for i, item in enumerate(iterable):
arr.append(iterable[i])
self.helper(result, arr, iterable, k)
arr.pop()
def get_bin_set(self, k):
result = set()
self.helper(result, [], '10', k)
return result
def hasAllCodes(self, s: str, k: int) -> bool:
bin_set = self.get_bin_set(k)
head, tail = 0, k
while tail <= len(s):
if s[head:tail] in bin_set:
bin_set.remove(s[head:tail])
if not bin_set:
return True
head += 1
tail += 1
return False
- 시간복잡도는 O(2^k)
- bin_set을 만들 때 2^k만큼 시간이 들어가고 while문을 돌 때 O(k)만큼 시간이 들어간다. -> O((2^k) + k) -> O(2^k)
- 공간복잡도는 O(2^k)
- arr.length가 k가 될 때까지 helper의 콜스택 O(k) 만큼 쌓이고, bin_set에 O(2^k)만큼 쌓인다.
세상에. 내가 이걸 왜 했지? 그동안 쌓인 스트레스 분출 같은건가?
II. Set을 사용한 정석 풀이
1, 출제자의 의도에 맞춰 O(n)으로 풀어본다. bin_set과 head, tail을 두고 체크하는 것은 같다.
1
2
3
4
5
6
7
8
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
bin_set = set()
head, tail = 0, k
while tail <= len(s): # 2-1
head += 1
tail += 1
2, 이번에는 반대로 substring들을 set에 저장한다. 중복된 경우라면 저장되지 않고 넘어갈 것이다.
1
2
3
4
5
6
7
8
9
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
bin_set = set()
head, tail = 0, k
while tail <= len(s):
bin_set.add(s[head:tail]) # 2-2
head += 1
tail += 1
binary string들의 조합은 k^2만큼씩 늘어난다.
when k = 1, [‘0’, ‘1’], length = 2 = 2^1
when k = 2, [‘00’, ‘10’, ‘01’, ‘11’], length = 4 = 2^2
when k = 3, [‘000’, ‘001’, ‘111’, ‘010’, ‘011’, ‘100’, ‘110’, ‘111’], length = 8 = 2^3
…
그럼 bin_set의 길이가 2^k, 즉 1 << k이 되면 모든 substring을 체크한 것이 된다. 만약 충족하지 못하면 False를 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
bin_set = set()
head, tail = 0, k
while tail <= len(s):
bin_set.add(s[head:tail])
if len(bin_set) == 1 << k: # 2-3
return True
head += 1
tail += 1
return False
- 시간복잡도는 O(sk)
- s.length와 k에 따라 비례적으로 시간이 증가한다.
- 공간복잡도는 O(2^k)
- bin_set에는 2^k개 만큼 쌓인다.