이진 문자열 s와 정수 k가 주어졌을 때, 길이가 k인 모든 이진 코드가 문자열 s의 부분 문자열로 존재하는지 확인하는 문제입니다. 만약 하나라도 존재하지 않는다면 false를 반환해야 합니다.
문제 이해하기
예를 들어 입력이 S = "00110110", k = 2라고 가정해 보겠습니다. 길이가 2인 이진 코드는 "00", "01", "10", "11" 네 가지이며, 각각 인덱스 0, 1, 3, 2 위치에서 발견할 수 있습니다. 따라서 이 경우 출력은 true가 됩니다.
접근 방법: 슬라이딩 윈도우 + 해시셋
이 문제는 슬라이딩 윈도우(sliding window) 기법과 해시셋(unordered_set)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 길이가 k인 모든 부분 문자열의 개수는 최대 2k개입니다.
- 문자열을 한 칸씩 이동하며 길이 k짜리 윈도우를 유지하고, 각 윈도우의 내용을 집합에 저장합니다.
- 집합의 크기가 2k에 도달하면 모든 코드가 존재한다는 뜻이므로 즉시 true를 반환합니다.
알고리즘 단계
- 집합 v를 하나 선언합니다.
- temp := 빈 문자열로 초기화합니다.
- req := 2k로 필요한 코드 개수를 계산합니다.
- i를 0부터 s의 크기까지 반복합니다.
- temp에 s[i]를 추가합니다.
- i >= k이면 temp의 첫 번째 문자를 삭제하여 윈도우 크기를 k로 유지합니다.
- i >= k - 1이면 완성된 길이 k의 부분 문자열 temp를 v에 삽입합니다.
- v의 크기가 req와 같아지면 true를 반환합니다.
- 반복이 끝날 때까지 조건을 만족하지 못하면 false를 반환합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli fastPow(lli b, lli p){
lli ret = 1;
while (p) {
if (p & 1) {
ret *= b;
}
b *= b;
p >>= 1;
}
return ret;
}
bool hasAllCodes(string s, int k) {
unordered_set<string> v;
string temp = "";
lli req = fastPow(2, k);
for (lli i = 0; i < s.size(); i++) {
temp += s[i];
if (i >= k) {
temp.erase(0, 1);
}
if (i >= k - 1) {
v.insert(temp);
}
if ((lli)v.size() == req)
return true;
}
return false;
}
};
main(){
Solution ob;
cout << (ob.hasAllCodes("00110110",2));
}입력
"00110110", 2
출력
1
복잡도 분석
- 시간 복잡도: O(n × k) — 문자열을 한 번 순회하면서 각 단계마다 길이 k의 부분 문자열을 처리합니다.
- 공간 복잡도: O(2k × k) — 최대 2k개의 길이 k 문자열을 집합에 저장할 수 있습니다.
마무리
이처럼 슬라이딩 윈도우로 길이 k의 모든 부분 문자열을 추출하고 해시셋으로 중복 없이 관리하면, 집합의 크기만으로 2k개의 이진 코드가 모두 등장했는지 빠르게 판별할 수 있습니다. 특히 집합 크기가 목표치에 도달하는 순간 조기 종료하므로 불필요한 연산을 줄일 수 있다는 점이 이 풀이의 장점입니다.