왜 이 문제에 대한 포스팅을 하는가?

이 문제는 clist 기준으로 2554 레이팅을 받은 굉장히 까다로운 문제다.
하지만 LeetCode 사이트에 들어가 보면 난이도가 Medium으로 표시되어 있다.
이 때문에 처음엔 “그래도 Medium인데?” 하고 방심했다가…
무려 1시간 동안 풀이 방식만 고민하는 상황이 벌어졌다.

다행히도 결국 나름 꽤 신박하고 깔끔한 풀이를 찾아냈고,
문제를 다 풀고 난 뒤 레이팅을 확인해보니 생각보다 난도가 더 높았다는 사실을 깨닫고
오히려 기분이 좋아져서 글을 작성해 보게 되었다. 😄

일요일을 망쳤다며 출제자를 원망하는 댓글 🤣

---

✨ 문제 요약 및 핵심 조건

문제는 다음을 요구한다.

1. 0과 1로 이루어진 문자열에서 모든 substring을 고려한다.
2. 그 중 dominant ones 조건을 만족하는 substring의 개수를 세면 된다.
3. dominant ones란,1의 개수 ≥ (0의 개수)^2 을 만족하는 substring이다.

여기서 substring은 연속된 구간을 의미한다.

---

❗ 단순한 완전 탐색이 불가능한 이유

길이가 n인 문자열에서 substring 개수는:

n + (n-1) + ... + 1 = (n * (n + 1)) / 2

문제에서는 n ≤ 40000 이므로: substring 개수 = 800,020,000 (약 8억 개)

약 8억 개다.

즉 모든 substring을 직접 만들어 검사하는 방식은 절대 불가능하다.

---

💡 핵심 아이디어 — “0”이 모든 것을 결정한다

dominant ones 조건을 다시 보면,

1의 개수 >= (0의 개수)^2

여기서 중요한 사실:

• 문자열에 0이 200개만 있어도 (200)^2 = 40000 즉, 문자열 전체 길이의 최대치에 도달한다.
• 0이 200개를 넘어가는 순간, 어떤 substring을 만들어도 1이 그만큼 많아질 수 없다.

즉, dominant한 substring 내부에서는, 0의 개수는 많아야 200개 정도라는 의미다.

이 관찰이 바로 문제 해결의 결정적인 포인트다.

---

🛠️ 구체적인 풀이 방식

핵심은 다음과 같은 흐름이다.

1. 문자열을 왼쪽부터 한 글자씩 순차적으로 탐색한다.

• 이 때, 등장한 모든 0의 위치를 저장해둔다.

2. 현재 인덱스 i에서 끝나는 substring만 생각한다.

• 왜냐면 “어디서 시작해서 i에서 끝나는 substring들”을 세면 전체 substring을 모두 커버할 수 있다.

3. i에서부터 거꾸로 0의 위치들을 탐색한다.

• 단, dominant한 substring은 0의 개수가 많아야 200개 정도이다.
• 따라서 매 위치 i에서 최대 200개의 0만 거꾸로 확인하면 충분하다.
• 이것이 시간 복잡도를 O(n × 200) = O(n)으로 만든다.

4. 0을 하나씩 확장하며 dominant 조건을 만족하는 substring 수를 계산한다.

• 현재 고려 중인 두 0 사이에는 연속된 1들이 있다.
• 이 1 덩어리의 길이를 이용해 “시작점을 어디까지 확장할 수 있는가?”를 빠르게 계산할 수 있다.
• 즉, 전체 substring을 구성하지 않고도 개수만 수학적으로 세는 방식이다.

이 작업을 i = 0부터 n-1까지 반복하면 된다.

---

🔍 전체 시간 복잡도

dominant substring에서 고려할 수 있는 0의 개수가 약 sqrt(n)이므로: O(n * sqrt(n))

문제의 조건(n ≤ 40000)에서는 충분히 빠르다.

---

✅ 전체 코드

class Solution {
public:
    typedef vector<int>vi;
    typedef vector<vi>vii;
    int numberOfSubstrings(string s) {
        vi z;
        int n=s.size();
        int answer=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0'){
                z.push_back(i);
            }
            
            int zeroCount=0;
            int oneCount=0;
            int lastIndex=i+1;

            for(int j=(int)z.size()-1;0<=j;j--){
                int pre=pow(zeroCount,2);
                int now=pow(++zeroCount,2);
                
                int between=lastIndex-z[j]-1;
                oneCount+=between;
                int diff=max(0,oneCount-pre+1);
                answer+=min(between,diff);

                if(oneCount>=now){
                    answer++;
                }
                
                lastIndex=z[j];
            
                if(now>i+1){
                    break;
                }
            }

            int pre=pow(zeroCount,2);
            int between=lastIndex;
            oneCount+=between;
            int diff=max(0,oneCount-pre+1);
            answer+=min(between,diff);
        }
        
        return answer;
    }
};

---

🏁 마무리

이 문제는 단순히 조건만 보면 평범해 보이지만,
substring이 워낙 많기 때문에 “직접 세지 않는 방식”을 찾아야 하는 고난도 문제다.

하지만 dominant ones라는 조건을 잘 보면
필연적으로 0의 개수가 제한된다는 사실을 알 수 있고,
이 점을 활용하면 매우 빠르게 문제를 해결할 수 있다.

문제를 푸는 데 애먹었지만, 결국 깔끔하게 해결할 수 있어서 개인적으로도 만족스러운 문제였다.