가장 가까운 같은 번호 사이의 거리
자바스크립트 코딩테스트 문제로 index-tracking 주제를 연습해보세요. 난이도는 easy이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
배열에서 값이 같은 두 원소를 골랐을 때, 인덱스 차이의 최솟값을 구하세요.
같은 값이 한 번도 반복되지 않으면 -1을 반환합니다.
제한사항
1 <= nums.length <= 100,000nums[i]는 정수입니다.- 반환값은 같은 값 두 개 사이의 가장 작은 인덱스 거리입니다.
- 같은 값이 없다면
-1을 반환합니다.
예시
- 입력:
[4, 1, 7, 4, 2, 7]→ 출력:3 - 입력:
[5, 3, 1, 3, 5]→ 출력:2 - 입력:
[9, 8, 7, 6]→ 출력:-1
힌트
- 어떤 숫자를 마지막으로 본 인덱스를 저장해 두면, 같은 숫자를 다시 만났을 때 바로 거리를 계산할 수 있습니다.
- 모든 쌍을 직접 비교하면 너무 느릴 수 있습니다.
해설
배열을 왼쪽부터 한 번만 순회합니다.
각 숫자에 대해 마지막으로 등장한 인덱스를 저장해 두고, 같은 숫자를 다시 만나면 현재 인덱스 - 마지막 인덱스를 계산합니다. 이 값을 지금까지의 최소 거리와 비교해 더 작은 값으로 갱신하면 됩니다.
예를 들어 [5, 3, 1, 3, 5]를 보면:
5를 인덱스0에서 처음 봅니다.3을 인덱스1에서 처음 봅니다.1을 인덱스2에서 처음 봅니다.3을 인덱스3에서 다시 보므로 거리3 - 1 = 25를 인덱스4에서 다시 보므로 거리4 - 0 = 4
최솟값은 2입니다.
이 방식은 각 원소를 한 번씩만 처리하므로 시간 복잡도는 O(n)이고, 마지막 위치 저장에 O(n) 추가 공간을 사용합니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.