Lv.2arrayhashsliding-windowtwo-pointers
같은 값이 없는 가장 긴 구간
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
놀이공원 퍼레이드에 참가한 차량 대가 한 줄로 지나가고, i번째 차량에는 캐릭터 번호 nums[i]가 붙어 있습니다.
사진가는 연속으로 지나가는 차량들을 한 장에 담으려 하는데, 같은 캐릭터가 두 번 찍히면 안 됩니다.
같은 값이 두 번 이상 나오지 않는 가장 긴 연속 구간(연속 부분 배열)의 길이를 반환하세요.
입출력 예
| nums | result |
|---|---|
[1, 2, 1, 3, 4, 3] | 4 |
[5, 5, 5] | 1 |
[7, 3, 9, 1] | 4 |
입출력 예 설명
예 1 — [2, 1, 3, 4]가 가장 깁니다. 여기서 한 칸만 늘려도 1 또는 3이 겹칩니다.
예 2 — 모든 값이 같으므로 한 대씩만 찍을 수 있습니다.
예 3 — 모든 값이 서로 다르므로 전체를 찍을 수 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(nums: int[]) → int
제한 사항
-
nums.length -
nums[i]
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| nums | 기대 출력 |
|---|---|
[1,2,1,3,4,3] | 4 |
[5,5,5] | 1 |
[7,3,9,1] | 4 |
힌트
힌트
오른쪽 끝 r을 한 칸씩 늘려 가면서, 구간의 왼쪽 끝 l은 뒤로 가지 않게 관리하세요(슬라이딩 윈도우).
각 값이 마지막으로 나온 위치를 해시 맵에 기억해 두면, nums[r]이 이미 구간 안(last ≥ l)에 있을 때
l = last + 1로 한 번에 옮길 수 있습니다. 그러면 전체가 입니다.
시작점마다 집합을 새로 만들어 겹칠 때까지 늘리는 풀이는 값이 대부분 서로 다를 때 이 되어 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1234 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |