Lv.1countingstring
0과 1이 반반인 구간
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
0과 1로 이루어진 문자열 s가 주어집니다. 다음 조건을 만족하는 연속 부분 문자열의 개수를 반환하세요.
0의 개수와1의 개수가 같다.- 모든
0이 한 덩어리로 붙어 있고, 모든1도 한 덩어리로 붙어 있다. 즉000111이나10처럼 생겼고,0101처럼 섞여 있지 않다.
내용이 같더라도 위치가 다른 부분 문자열은 따로 셉니다.
입출력 예
| s | result |
|---|---|
"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
제한 사항
-
s.length 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, … 처럼 경계에서 양쪽으로 같은 길이만큼 펼친 것).
따라서 문자열을 한 번 훑으며 직전 덩어리 길이와 현재 덩어리 길이만 기억하면 됩니다.
복잡도 목표
시작 위치마다 오른쪽으로 늘려 가며 확인하면 긴 덩어리가 있을 때 이 되어 시간 초과입니다. 덩어리 길이를 쓰면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |