[99클럽 코테 스터디] 22일차 TIL - 정렬, Find Target Indices After Sorting Array

[22일차] 정렬

문제: https://leetcode.com/problems/find-target-indices-after-sorting-array/description/

* 번역: 0부터 시작하는 인덱스를 가진 정수 배열 nums와 목표 요소 target가 주어진다.

목표 인덱스란 nums[i] == target이 되는 인덱스 i를 의미한다.

nums를 비내림차순(오름차순)으로 정렬한 후 목표 인덱스의 리스트를 반환하라. 만약 목표 인덱스가 없다면 빈 리스트를 반환하세요. 반환된 리스트는 오름차순으로 정렬되어 있어야 한다.

Solution

정렬 메소드 sort()를 활용하면 쉽게 해결할 수 있다. 그러나 해당 메소드의 시간 복잡도는 O(nlogn)이다. 

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        ans = []
        nums.sort()

        for i in range(len(nums)):
            if nums[i] == target:
                ans.append(i)

        return ans

Another Solution

시간 복잡도 O(n)인 풀이는 다음과 같다. 정렬 메소드를 사용하지 않고 순회를 통해서도 문제를 해결할 수 있다. 실제로 정렬된 배열을 만들어 인덱스를 '찾기'보다, 오름차순 정렬이라는 개념을 활용하여 인덱스를 '계산'하는 방식이다.

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        lessThanEqual = 0
        onlyLess = 0
        for i in nums:
            if i <= target:
                lessThanEqual += 1
            if i < target:
                onlyLess += 1
        return list(range(onlyLess, lessThanEqual))

나다어

나는 다음에 어떻게 할까

 

• 시간 복잡도가 중요한 응용 문제가 될 경우, 문제에서 요구하는 것을 "그대로" 구현하는 방법보다 문제가 요구하는 결과를 낼 수 있는 방법이 무엇인지 생각해보자.