문제 개요
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 보겠습니다. 두 수 nums[i] ≤ nums[j] 사이에 다른 어떤 수도 존재하지 않을 때, 이 두 수를 '인접(adjacent)'하다고 정의합니다. 우리가 구해야 할 것은 인접한 두 수 nums[i]와 nums[j]에 대해 가능한 최소의 |j − i| 값입니다.
예를 들어 입력이 nums = [1, -9, 6, -6, 2]라면 출력은 2가 됩니다. 이 리스트에서 2와 6은 서로 인접한 값이며, 두 요소의 인덱스 차이가 정확히 2이기 때문입니다.
해결 전략
이 문제는 다음 단계를 따라 해결할 수 있습니다.
각 값이 등장한 위치를 저장할 딕셔너리(indexes)를 생성합니다.
리스트 A를 순회하면서 값 x가 나타난 인덱스 i를 indexes[x] 목록의 끝에 추가합니다.
ans를 리스트 A의 길이로 초기화합니다.
동일한 값을 가진 요소들은 항상 서로 인접하므로, 각 값별 인덱스 목록에서 연속된 인덱스의 차이를 계산해 ans를 갱신합니다.
딕셔너리의 키(값)들을 오름차순으로 정렬합니다.
정렬된 값들 중 이웃한 두 값에 해당하는 인덱스 목록 r1과 r2를 가져온 뒤, 투 포인터(two-pointer) 기법으로 두 목록 간의 최소 인덱스 차이를 구해 ans를 갱신합니다.
모든 탐색이 끝나면 ans를 반환합니다.
핵심 아이디어
이 풀이의 핵심은 크게 두 가지로 나눌 수 있습니다. 첫째, 같은 값을 가진 요소들끼리는 조건상 반드시 인접하므로, 값별 인덱스 목록 내에서 연속된 인덱스 간격만 확인하면 됩니다. 둘째, 서로 다른 값이 인접하려면 두 값 사이에 다른 값이 존재하지 않아야 하므로, 정렬된 값 순서에서 바로 옆에 있는 값들끼리만 비교하면 충분합니다. 이때 두 인덱스 목록을 병합 과정처럼 투 포인터로 훑으면 불필요한 비교 없이 최소 차이를 효율적으로 찾을 수 있습니다.
파이썬 구현 예제
아래 코드를 통해 구현 방법을 더 자세히 살펴보겠습니다.
from collections import defaultdict
class Solution:
def solve(self, A):
indexes = defaultdict(list)
for i, x in enumerate(A):
indexes[x].append(i)
ans = len(A)
for row in indexes.values():
for i in range(len(row) - 1):
ans = min(ans, row[i + 1] - row[i])
vals = sorted(indexes)
for k in range(len(vals) - 1):
r1 = indexes[vals[k]]
r2 = indexes[vals[k + 1]]
i = j = 0
while i < len(r1) and j < len(r2):
ans = min(ans, abs(r1[i] - r2[j]))
if r1[i] < r2[j]:
i += 1
else:
j += 1
return ans
ob = Solution()
nums = [1, -9, 6, -6, 2]
print(ob.solve(nums))
입력
[1, -9, 6, -6, 2]
출력
2
복잡도 분석
시간 복잡도는 O(n log n)입니다. 고유한 값들을 정렬하는 데 O(n log n)이 소요되며, 이후 진행되는 투 포인터 탐색은 전체적으로 선형 시간 안에 처리됩니다. 공간 복잡도는 모든 요소의 인덱스를 저장해야 하므로 O(n)입니다.