Lv.4dpstring
팰린드롬 조각으로 자르기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
문자열 s를 몇 번 잘라서 모든 조각이 팰린드롬(앞에서 읽으나 뒤에서 읽으나 같은 문자열)이 되게 하려고 합니다.
필요한 최소 자르기 횟수를 반환하세요. s가 이미 팰린드롬이면 0입니다.
입출력 예
| s | result |
|---|---|
"aab" | 1 |
"racecar" | 0 |
"abcd" | 3 |
입출력 예 설명
예 1 — "aa" | "b"로 한 번 자르면 됩니다.
예 3 — 글자마다 잘라야 합니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(s: string) → int
제한 사항
-
s.length s는 영어 소문자로만 이루어져 있습니다.
기대 복잡도
- 시간
- O(N^2)
- 공간
- O(N)
입출력 예
| s | 기대 출력 |
|---|---|
"aab" | 1 |
"racecar" | 0 |
"abcd" | 3 |
힌트
힌트
cut[i] = "s의 앞 i글자를 팰린드롬 조각들로 나누는 데 필요한 최소 조각 수"로 두면,
마지막 조각 s[j..i)가 팰린드롬인 모든 j에 대해 cut[i] = min(cut[j] + 1)입니다. 답은 cut[n] - 1입니다.
문제는 "s[j..i)가 팰린드롬인가"를 매번 직접 확인하면 씩 걸린다는 점입니다. 두 가지 방법이 있습니다.
- 중심 확장: 각 중심에서 양옆으로 넓혀 가며 찾은 팰린드롬
s[l..r]마다 바로cut[r+1] = min(cut[r+1], cut[l] + 1)로 갱신합니다. 추가 메모리가 거의 없습니다. - 팰린드롬 표:
pal[j][i] = (s[j] == s[i]) && pal[j+1][i-1]을 미리 채워 에 확인합니다(메모리 ).
복잡도 목표
조각마다 팰린드롬인지 직접 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| 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 | 7 | 판정만 |
| performance | 60 | 4 | 판정만 |