배열 nums와 두 개의 값 target(반드시 nums 안에 존재해야 함), start가 주어졌다고 가정해 봅시다. 이때 nums[i] = target을 만족하는 인덱스 i 중에서 |i - start|의 값이 가장 작은 경우를 찾고, 그 최솟값을 반환해야 합니다.
예를 들어 입력이 nums = [3,4,5,6,7], target = 7, start = 2라고 해 보겠습니다. 이 경우 출력은 2가 됩니다. target과 일치하는 값은 nums[4] 하나뿐이므로 i = 4이고, 따라서 |4 - 2| = 2이기 때문입니다.
문제 해결 접근 방법
이 문제는 단순한 선형 탐색(완전 탐색)으로 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 최솟값을 저장할 변수
minimum을 무한대(infinity)로 초기화합니다. - 0부터 배열
nums의 길이까지 인덱스 i를 순회하며 다음을 검사합니다.nums[i]가target과 같은지 확인합니다.- 같다면
|i - start|가 현재minimum보다 작은지 비교합니다. - 더 작다면
minimum을|i - start|값으로 갱신합니다.
- 순회가 끝나면
minimum을 반환합니다.
구현 예제 코드
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
from math import inf
def solve(nums, target, start):
minimum = inf
for i in range(len(nums)):
if nums[i] == target:
if abs(i - start) < minimum:
minimum = abs(i - start)
return minimum
nums = [3,4,5,6,7]
target = 7
start = 2
print(solve(nums, target, start))
입력
[3,4,5,6,7], 7, 2
출력
2
복잡도 분석
이 알고리즘은 배열의 모든 요소를 한 번씩 확인하므로 시간 복잡도는 O(n)입니다. 여기서 n은 배열의 길이입니다. 추가로 사용되는 공간은 최솟값을 저장하는 변수 하나뿐이므로 공간 복잡도는 O(1)로 매우 효율적입니다.
참고로, 만약 target이 배열에 여러 번 등장한다면 이 코드는 자동으로 시작 지점에 가장 가까운 위치의 거리를 반환합니다. 또한 Python의 math.inf 대신 임의의 큰 값(예: len(nums))으로 초기화해도 동일하게 동작합니다.