K-Distant 인덱스 찾기 문제 요약

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

웹 개발

대상자

소프트웨어 개발자 및 알고리즘 문제 풀이 준비자
난이도: 중간
포인터 기반 그리디 알고리즘 이해가 필요
중복된 인덱스 검사를 방지하는 전략 필요

핵심 요약

그리디 알고리즘과 포인터를 활용한 O(n) 시간 복잡도 접근법
start 포인터로 중복된 인덱스 검사 방지
nums[j] == key인 인덱스 j 주변 k 범위의 인덱스 i를 모두 포함
i - k <= j <= i + k 조건 적용
C++, Python, JavaScript 구현 예시 포함
start 변수는 min(n-1, i + k) 범위 내에서만 처리

섹션별 세부 요약

1. 문제 정의

입력: 배열 nums, 정수 key, 정수 k
출력: nums[j] == key인 인덱스 j와 |i - j| <= k 조건을 만족하는 인덱스 i의 오름차순 배열
예시: nums = [1,2,3,4,5], key = 3, k = 1 → i = 2, 3, 4

2. 알고리즘 접근법

Greedy + 포인터 전략
key가 있는 인덱스 j를 기준으로 j - k부터 j + k까지 인덱스 i 추가
start 포인터로 이전에 처리한 인덱스 재검사 방지
시간 복잡도: O(n) (배열 한 번만 순회)
공간 복잡도: O(1) (결과 배열 제외)

3. 코드 구현

C++

```cpp

vector findKDistantIndices(vector& nums, int key, int k) {

vector ans;

int n = nums.size();

int start = 0;

for(int i=0; i

if(nums[i] == key) {

int left = max(0, i - k);

int right = min(n-1, i + k);

while(start <= right) {

if(start >= left) ans.push_back(start);

start++;

}

return ans;

}

```

Python

```python

def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:

ans = []

n = len(nums)

start = 0

for i in range(n):

if nums[i] == key:

left = max(0, i - k)

right = min(n - 1, i + k)

while start <= right:

if start >= left:

ans.append(start)

start += 1

return ans

```

4. 효율성 분석

중복된 인덱스 검사 방지: start 포인터로 left 범위 이전의 인덱스는 무시
선형 시간 복잡도: n 번의 루프로 O(n)
공간 최적화: start 변수만 사용

결론

Greedy 알고리즘과 포인터 전략을 활용한 효율적 접근법
start 포인터로 중복 검사 최소화
실무 적용 팁:
key가 빈번하게 나타나는 경우 k 범위가 겹칠 수 있으므로 start 변수 관리 중요
k 값이 배열 길이보다 클 경우 left = 0, right = n-1로 자동 조정
최종 출력 예시: nums = [2,2,2,2,2], key = 2, k = 1 → [0,1,2,3,4]