문제 개요
이번 글에서는 흥미로운 문자열 문제를 다뤄보겠습니다. 주어진 이진(binary) 문자열이 다음 조건을 모두 만족하는지 판별하는 코드를 작성해야 합니다.
- 연속된 1로 이루어진 모든 그룹의 길이는 반드시 2여야 합니다. 즉, 1은 "11" 형태로만 나타날 수 있습니다.
- 연속된 1의 그룹은 반드시 하나 이상의 0 뒤에 나타나야 합니다. 따라서 문자열이 1로 시작해서는 안 됩니다.
예를 들어 "0110"은 조건을 만족하는 유효한 문자열입니다. 반면 "001110"은 1이 세 개 연속으로 나오므로, "010"은 1이 하나만 나오므로 각각 유효하지 않습니다.
접근 방법
풀이 접근법은 매우 단순합니다. 문자열에서 1이 나타나는 위치를 차례대로 찾고, 해당 위치가 올바른 "011" 패턴의 일부인지 확인하면 됩니다. 검증 규칙은 다음과 같습니다.
- 1 앞에는 반드시 0이 있어야 합니다(그룹이 0 뒤에 나와야 한다는 조건).
- 1 뒤에는 반드시 또 다른 1이 이어져야 하며, 그 다음 위치에는 1이 더 있으면 안 됩니다. 즉 "111" 형태는 허용되지 않습니다.
- 문자열 마지막에 홀로 남은 1이 있으면 안 됩니다.
- 문자열 첫 번째 문자가 1이면 처음부터 유효하지 않습니다.
검사 과정에서 어떤 위치라도 위 조건 중 하나라도 어기면 즉시 false를 반환하고, 모든 조건을 통과하면 true를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
bool isValidStr(string str) {
int n = str.length();
int index = find(str.begin(), str.end(), '1') - str.begin();
if (index == 0) // 문자열이 1로 시작하면 false 반환
return false;
while (index <= n - 1) {
if (str[index - 1] != '0') // 1이 0 뒤에 나오지 않는 경우
return false;
if (index + 1 < n && str[index + 1] != '1') // 1 뒤에 또 다른 1이 없는 경우
return false;
if (index + 2 < n && str[index + 2] == '1') // "0111" 형태인 경우
return false;
if (index == n - 1) // 문자열이 하나의 1로 끝나는 경우
return false;
index = find(str.begin() + index + 2, str.end(), '1') - str.begin();
}
return true;
}
int main() {
string str = "011000110110";
if(isValidStr(str)){
cout << str << " is a valid string";
} else {
cout << str << " is NOT a valid string";
}
}실행 결과
011000110110 is a valid string
코드 설명 및 복잡도
위 예제의 입력 문자열 "011000110110"에서 1 그룹들은 모두 정확히 두 개씩 연속으로 나타나며, 각 그룹 앞에는 0이 존재합니다. 따라서 유효한 문자열로 판별됩니다.
알고리즘은 find 함수를 이용해 다음 1의 위치를 찾아가며 문자열을 선형으로 순회하므로, 시간 복잡도는 O(n)이고 추가 메모리 사용량은 O(1)입니다. 이 방식은 문자열 길이가 커져도 효율적으로 동작합니다.