Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 문자열에 길이 k의 모든 이진 순열이 포함되어 있는지 확인하는 방법

이진(binary) 문자열 하나와 정수 k가 주어졌을 때, 해당 문자열이 k비트 이진수의 모든 순열을 포함하고 있는지 확인하는 문제입니다.

예를 들어 문자열이 "11001"이고 k = 2라고 가정해 보겠습니다. 이 경우 2비트 이진수의 모든 순열인 00, 01, 10, 11 네 가지가 반드시 문자열 안에 존재해야 합니다. "11001"에는 길이 2의 부분 문자열로 "11", "10", "00", "01"이 모두 등장하므로 유효한(valid) 문자열입니다.

문제 해결 접근 방식

주어진 이진 문자열과 k값을 이용해 필요한 이진 시퀀스가 모두 일치하는지 검사해야 합니다. 이진 시퀀스의 길이가 k이므로 서로 다른 이진 순열의 개수는 총 2k개입니다.

해결 과정은 다음과 같습니다.

  1. 길이가 k인 모든 이진 값을 문자열 형태로 생성하여 리스트에 저장합니다. 이때 이진수 증가 규칙(오른쪽 자릿수부터 0 → 1로 바꾸고 자릿수 올림 처리)을 그대로 흉내 내면 중복 없이 모든 순열을 빠짐없이 만들 수 있습니다.
  2. 생성된 각 순열이 주어진 문자열의 부분 문자열(substring)로 존재하는지 find() 함수로 확인합니다.
  3. 리스트의 모든 문자열이 발견되면 true(유효), 단 하나라도 발견되지 않으면 false(유효하지 않음)를 반환합니다.

C++ 구현 예제

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 길이가 k인 모든 이진 순열을 생성하여 벡터로 반환
vector<string> binaryPermutations(int k){
    vector<string> list;
    string bin_str = "";
    // k개의 '0'으로 초기화 (예: k=2 → "00")
    for(int i = 0; i < k; i++){
        bin_str += "0";
    }
    int limit = pow(2, k);
    list.push_back(bin_str);
    // 이진수 증가 방식으로 나머지 순열 생성
    for(int i = 1; i < limit; i++){
        int j = 0;
        while(j <= k){
            if(bin_str[k-1-j] == '0'){
                bin_str[k - 1 - j] = '1';
                break;
            } else {
                bin_str[k - 1 - j] = '0';
                j++;
            }
        }
        list.push_back(bin_str);
    }
    return list;
}

// 문자열 str이 길이 k의 모든 이진 순열을 포함하는지 검사
bool hasAllPermutation(string str, int k){
    vector<string> list = binaryPermutations(k);
    for(int i = 0; i < list.size(); i++){
        string substr = list[i];
        std::size_t found = str.find(substr);
        if(found == std::string::npos){
            return false;   // 하나라도 없으면 실패
        }
    }
    return true;            // 모두 존재하면 성공
}

int main() {
    int k = 2;
    string str = "11001";
    if(hasAllPermutation(str, k)){
        cout << "Has All Permutations";
    } else {
        cout << "Not All Permutations are found";
    }
}

실행 결과

Has All Permutations

복잡도 분석

  • 시간 복잡도: O(2k × n × k) — 총 2k개의 순열을 생성하고, 각 순열마다 길이 n인 원본 문자열에서 부분 문자열 탐색(O(n × k))을 수행합니다.
  • 공간 복잡도: O(2k × k) — 생성된 모든 순열 문자열을 리스트에 저장해야 하기 때문입니다.

참고: 더 효율적인 대안

모든 순열을 미리 만들어 두는 대신, 슬라이딩 윈도우(sliding window) 기법으로 길이가 k인 모든 부분 문자열을 한 번씩만 살펴보며 집합(set)에 담은 뒤, 집합의 크기가 2k와 같은지 비교하는 방법도 있습니다. 이 방식은 시간 복잡도를 O(n × k) 수준까지 줄일 수 있어 문자열이 긴 경우에 특히 유용합니다.