이진 문자열 S와 양의 정수 N이 주어졌을 때, 1부터 N까지의 모든 정수 X에 대해 X의 이진 표현이 문자열 S의 부분 문자열로 존재한다면 true를 반환해야 합니다.
예를 들어 S = "0110"이고 N = 3이라면 결과는 true입니다. 1은 "1", 2는 "10", 3은 "11"로 표현되며, 이 세 값이 모두 "0110" 안에 포함되어 있기 때문입니다.
문제 해결 접근 방법
정수 n을 입력받아 이진 문자열로 변환하는 convert() 메서드를 정의합니다.
ret := 빈 문자열로 초기화합니다.
n이 0이 아닌 동안 다음을 반복합니다.
ret := ret에 (n mod 2)를 이어 붙임
n := n / 2
ret을 역순으로 뒤집은 후 반환합니다.
main 메서드에서는 다음을 수행합니다.
i := N부터 시작하여 i >= N/2를 만족하는 동안 i를 1씩 감소시키며 반복합니다.
temp := convert(i)
temp가 S에 존재하지 않으면 false를 반환합니다.
모든 검사를 통과하면 true를 반환합니다.
N/2까지만 검사해도 되는 이유
이 풀이에는 흥미로운 최적화가 숨어 있습니다. 임의의 수 m이 N/2 이하라면, 2m과 2m+1은 항상 N 이하이며, 이 두 수의 이진 표현은 m의 이진 표현 끝에 비트 '0' 또는 '1'을 하나 붙인 것과 같습니다. 따라서 N부터 N/2까지의 모든 수가 S의 부분 문자열이라면, 마지막 비트를 제거하는 방식으로 그보다 작은 수들 역시 자동으로 부분 문자열임이 보장됩니다. 덕분에 전체 범위를 검사하지 않고도 절반만 확인해 정답을 구할 수 있습니다.
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string convert(int n){
string ret = "";
while(n){
ret += (n % 2) + '0';
n /= 2;
}
reverse(ret.begin(), ret.end());
return ret;
}
bool queryString(string S, int N) {
for(int i = N; i >= N/2; i-- ){
string temp = convert(i);
if(S.find(temp) == string::npos) return false;
}
return true;
}
};
main(){
Solution ob;
cout << (ob.queryString("0110", 3));
}입력
"0110" 3
출력
1
출력값 1은 true, 즉 조건을 만족한다는 의미입니다.