1365. How Many Numbers Are Smaller Than the Current Number

How Many Numbers Are Smaller Than the Current Number - LeetCode

 

0 ~ 100으로 이루어진 정수 배열이 주어진다.

해당하는 인덱스가 가리키는 정수보다 큰 정수가 배열에 몇 개 있는지 세어서 반환하는 문제다.

# 예시

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

1. Brute Force

from typing import *


class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        answer = []
        for i in range(len(nums)):
            temp = 0
            for num in nums:
                temp += 1 if nums[i] > num else 0
            answer.append(temp)
        return answer

문제는 쉽다. 입력 제한도 빡빡하지 않기 때문에 그냥 2중 for문으로 전부 체크하면 된다.

그리고 보통 이런 문제는 최적화하는 방법이 있는데...

 

2. Counting + Prefix sum

from typing import *


class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        answer, count, prefix = [], [0] * 101, [0] * 101
        for num in nums:
            count[num] += 1

        for i in range(101):
            if i == 0:
                prefix[i] = count[i]
            else:
                prefix[i] = count[i] + prefix[i - 1]

        for num in nums:
            if num == 0:
                answer.append(0)
            else:
                answer.append(prefix[num - 1])

        return answer

거의 시간이 8배가 줄었다.

Counting, Prefix sum을 활용하면 O(N)으로 해결할 수 있다.

시나리오는 다음과 같다.

 

1. 입력된 배열의 정수 개수를 세어 count배열에 저장한다.

2. prefix 배열을 만들고, prefix 배열의 i 인덱스의 값 = count [i] + prefix [i-1]을 반복한다.

이 과정에서 얻은 prefix [i]가 의미하는 것은 입력된 배열에서 정수 i보다 같거나 작은 정수의 개수를 담게 된다.

3. 결국 prefix [i-1]은 i보다 작은 정수의 개수를 담고 있는 값이기 때문에 원하는 결과를 얻을 수 있다.

추가적으로 0의 경우는 입력 제한 범위가 0 ~ 100이기 때문에 0보다 작은 값은 존재하지 않아서 0을 넣었다.

 

작년 K사 기출도 그렇고 가끔 prefix sum을 활용하는 문제가 나오는 것 같다.