Funcia
Lv.1countingstring

0과 1이 반반인 구간

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

0과 1로 이루어진 문자열 s가 주어집니다. 다음 조건을 만족하는 연속 부분 문자열의 개수를 반환하세요.

  • 0의 개수와 1의 개수가 같다.
  • 모든 0이 한 덩어리로 붙어 있고, 모든 1도 한 덩어리로 붙어 있다. 즉 000111이나 10처럼 생겼고, 0101처럼 섞여 있지 않다.

내용이 같더라도 위치가 다른 부분 문자열은 따로 셉니다.

입출력 예

sresult
"00110011"6
"10101"4
"000"0

입출력 예 설명

예 1 — "0011", "01", "1100", "10", "0011", "01" 여섯 개입니다. "00110011" 전체는 0과 1의 개수가 같지만 덩어리가 나뉘어 있어서 세지 않습니다.

예 2 — "10", "01", "10", "01" 네 개입니다.

예 3 — 1이 없으므로 조건을 만족하는 부분 문자열이 없습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(s: string) → int

제한 사항

  • 1≤1 \le s.length ≤500,000\le 500{,}000
  • s는 0과 1로만 이루어져 있습니다.

기대 복잡도

시간
O(N)
공간
O(1)

입출력 예

s기대 출력
"00110011"6
"10101"4
"000"0

힌트

힌트

조건을 만족하는 부분 문자열은 항상 같은 글자가 이어진 덩어리 두 개가 맞닿은 자리에 걸쳐 있습니다.

s를 덩어리 길이로 바꿔 보세요. 예를 들어 "00110011"은 [2, 2, 2, 2], "0001111"은 [3, 4]입니다. 이웃한 두 덩어리 길이가 a, b이면 그 경계에 걸친 답은 정확히 min(a, b)개입니다(01, 0011, … 처럼 경계에서 양쪽으로 같은 길이만큼 펼친 것).

따라서 문자열을 한 번 훑으며 직전 덩어리 길이와 현재 덩어리 길이만 기억하면 됩니다.

복잡도 목표

시작 위치마다 오른쪽으로 늘려 가며 확인하면 긴 덩어리가 있을 때 O(N2)O(N^2)이 되어 시간 초과입니다. 덩어리 길이를 쓰면 O(N)O(N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.