C++로 이진 문자열에서 1 사이에 0이 있는지 확인하는 방법

문제 개요

이번 글에서는 흥미로운 문자열 문제를 다뤄보겠습니다. 주어진 이진 문자열(binary string)에서 1로 이루어진 구간 사이에 0이 존재하는지를 판별하는 것입니다. 만약 1과 1 사이에 0이 없다면 그 문자열은 유효(valid)하고, 하나라도 있다면 유효하지 않은(invalid) 문자열입니다.

예를 들어, 다음과 같은 세 개의 문자열이 있다고 가정해 보겠습니다.

A: 10001111010
B: 00001111100
C: 01111101111

이 세 문자열 중 오직 B만 유효합니다. B는 앞부분의 0들 뒤에 1이 연속해서 나타나며, 1들의 스트림 내부에는 0이 전혀 없기 때문입니다. 반면 A와 C는 1 사이에 0이 끼어 있어 유효하지 않습니다.

해결 접근 방식

이 문제는 간단한 인덱스 탐색으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

문자열에서 첫 번째 '1'의 위치(인덱스)를 찾습니다.
문자열에서 마지막 '1'의 위치(인덱스)를 찾습니다.
두 인덱스 사이 구간을 순회하면서 '0'이 하나라도 존재하는지 확인합니다.
'0'이 발견되면 false를 반환하고, 끝까지 발견되지 않으면 true를 반환합니다.

첫 번째 1과 마지막 1 사이에 있는 모든 문자가 1이라면, 그 문자열은 유효하다고 볼 수 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

bool hasZeroInOnes(string str) {
    int first, last;

    // 첫 번째 '1'의 인덱스 찾기
    for(first = 0; first < str.length(); first++){
        if(str[first] == '1')
            break;
    }

    // 마지막 '1'의 인덱스 찾기
    for(last = str.length() - 1; last >= 0; last--){
        if(str[last] == '1')
            break;
    }

    // 두 인덱스 사이에 '0'이 있는지 검사
    for(int i = first + 1; i < last; i++){
        if(str[i] == '0')
            return false;
    }

    return true;
}

int main() {
    string str = "00001111100";

    if(hasZeroInOnes(str)){
        cout << str << " is a valid string";
    } else {
        cout << str << " is NOT a valid string";
    }
}

실행 결과

00001111100 is a valid string

코드 설명 및 시간 복잡도

위 코드는 세 번의 선형 순회를 수행합니다. 첫 번째 루프는 왼쪽부터 처음 나오는 '1'을 찾고, 두 번째 루프는 오른쪽부터 마지막 '1'을 찾으며, 세 번째 루프는 두 위치 사이에 '0'이 있는지 검사합니다.

각 루프가 문자열 길이 n에 비례하여 실행되므로, 전체 시간 복잡도는 O(n)입니다. 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.

참고로, 문자열에 '1'이 하나도 없는 경우 first와 last 변수의 값이 범위를 벗어날 수 있으므로, 실제 응용에서는 이러한 엣지 케이스(edge case)에 대한 추가 처리를 고려하는 것이 좋습니다.