Lv.1arraystringtwo-pointers
가장 가까운 정류장까지의 거리
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
일직선 도로를 한 칸씩 나눠 각 칸의 시설을 영어 소문자로 적은 문자열 road가 있습니다. 그중 문자 c가 적힌 칸이 버스 정류장입니다.
각 칸 i마다 가장 가까운 정류장까지의 거리 |i - j|(road[j] == c)를 구해, 칸 순서대로 담은 배열을 반환하세요. 정류장 칸 자신의 거리는 0입니다. road에는 c가 적어도 한 번 나타납니다.
입출력 예
| road | c | result |
|---|---|---|
"loveleetcode" | 'e' | [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0] |
"aaab" | 'b' | [3, 2, 1, 0] |
"x" | 'x' | [0] |
입출력 예 설명
예 1 — e는 3, 5, 6, 11번 칸에 있습니다. 예를 들어 8번 칸에서 가장 가까운 정류장은 6번 칸이고, 거리는 2입니다.
예 2 — 정류장은 맨 끝 한 곳뿐입니다.
예 3 — 칸이 하나뿐이고 그 칸이 정류장입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(road: string, c: char) → int[]
제한 사항
-
road.length road는 영어 소문자로만 이루어져 있습니다.c는 영어 소문자 한 글자이며,road에 적어도 한 번 나타납니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| road | c | 기대 출력 |
|---|---|---|
"loveleetcode" | "e" | [3,2,1,0,1,0,0,1,2,2,1,0] |
"aaab" | "b" | [3,2,1,0] |
"x" | "x" | [0] |
힌트
힌트
가장 가까운 정류장은 왼쪽에 있거나 오른쪽에 있거나 둘 중 하나입니다.
- 왼쪽에서 오른쪽으로 훑으면서 "마지막으로 본 정류장 위치"를 기억하면, 각 칸에서 왼쪽 정류장까지의 거리를 알 수 있습니다.
- 오른쪽에서 왼쪽으로 한 번 더 훑으며 오른쪽 정류장까지의 거리를 구하고, 둘 중 작은 값을 고르세요.
아직 정류장을 보지 못한 쪽은 매우 먼 거리로 취급하면 됩니다.
복잡도 목표
칸마다 양옆으로 한 칸씩 넓혀 가며 정류장을 찾으면, 정류장이 드물 때 이 되어 시간 초과입니다. 두 번 훑으면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1142 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |