[리트코드 2089] 정렬 후 타깃 인덱스 찾기 — 타깃보다 작은 원소 수로 시작 위치 계산

원제: Find Target Indices After Sorting Array

문제 요약

정수 배열을 오름차순 정렬했을 때 target과 같은 원소가 놓일 인덱스들을 오름차순으로 반환합니다. 제출 코드는 배열 자체를 정렬하지 않고, target보다 작은 원소의 개수와 target의 개수만 세어 반환 목록을 만듭니다.

조건과 입출력

배열 nums는 0부터 시작하는 정수 배열이며, 1 <= nums.length <= 100, 1 <= nums[i], target <= 100입니다. 반환 목록에는 정렬한 배열에서 nums[i] == target인 인덱스를 모두 담아야 하고, 결과가 없으면 빈 목록을 반환합니다. 결과 인덱스는 오름차순입니다.

예제와 문제 자료

예제 1: nums = [1,2,5,2,3], target = 2이면 결과는 [1,2]입니다. 2보다 작은 원소가 하나이고 2가 두 개이므로, 타깃 인덱스는 1부터 두 칸입니다. 예제 2: 같은 배열에서 target = 3이면 결과는 [3]입니다. 3보다 작은 원소가 세 개이고 3은 한 개입니다.

풀이 아이디어

오름차순 정렬 결과에서 target보다 작은 값들은 모두 타깃보다 앞에 놓입니다. 따라서 그 값의 개수가 첫 타깃의 인덱스가 됩니다. 타깃이 cnt개라면 같은 값들이 정렬 후 연속해서 놓이므로 인덱스는 idx부터 idx + cnt - 1까지입니다. 코드의 idx와 cnt는 이 두 개수를 각각 세며, 다른 값들의 상대적인 순서는 결과 인덱스 계산에 필요하지 않아 실제 정렬을 하지 않아도 됩니다.

코드의 핵심

for num in nums에서 각 원소를 확인합니다. num < target이면 정렬 후 타깃 앞에 올 원소이므로 idx += 1을 하고, num == target이면 결과에 포함될 타깃 개수이므로 cnt += 1을 합니다. num > target인 경우에는 두 값 모두 바뀌지 않습니다. 마지막의 [idx+i for i in range(cnt)]는 i를 0부터 cnt - 1까지 증가시키며 연속 인덱스를 만듭니다. 예제 1을 코드에 따라 추적하면 1에서 idx가 1, 첫 번째 2에서 cnt가 1, 5에서는 변화 없음, 두 번째 2에서 cnt가 2, 3에서는 변화가 없습니다. 최종적으로 idx = 1, cnt = 2이므로 [1,2]를 반환합니다.

제출 코드

class Solution:
    def targetIndices(self, nums: list[int], target: int) -> list[int]:
        idx = 0
        cnt = 0
        for num in nums:
            if num < target:
                idx += 1

            elif num == target:
                cnt += 1

        return [idx+i for i in range(cnt)]

복잡도

입력 원소 수를 n, target의 개수를 cnt라고 하면 한 번의 순회에 O(n), 결과 목록 생성에 O(cnt)가 들어 시간 복잡도는 O(n + cnt)입니다. 반복문에서 쓰는 보조 변수 공간은 O(1)이고, 반환 목록 저장 공간은 O(cnt)입니다.

복습 포인트

target이 없으면 cnt = 0이므로 range(cnt)가 비어 있고 결과는 []입니다. 배열은 코드에서 변경하거나 실제로 정렬하지 않으며, 반환 목록은 정렬 후의 인덱스만 표현합니다.

출처

문제 원문