•
문제 설명 : 제공된 nums 각 요소들보다 작은 다른 요소의 갯수를 확인하여 리스트로 반환
•
풀이 방법
◦
default value값이 0인 default dict를 선언하고, 각 숫자를 순회하면서 각 숫자보다 큰 key를 가진 value에 모두 1을 더해주었다.
•
시간복잡도 :
•
성공 코드
from collections import defaultdict
# O(N + N^2 + N) -> O(N^2)
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
count_info = defaultdict(int)
# nums 순회 -> O(N)
max_num = max(nums)
# O(N)
for num in nums:
# O(N)
# 현 숫자 ~ nums에서 가장 큰 숫자까지 key를 가진 value에 갯수 추가
for i in range(num + 1, max_num + 1):
count_info[i] += 1
# 각 num보다 작은 key값의 value 갯수를 컨프리헨션으로 만들어 반환
# O(N)
return [count_info[num] for num in nums]
Python
복사
•
시간 복잡도가 더 낮은 다른 코드(다른 사람 코드)
sorted / sort 메서드가 O(NlogN) 으로 최적화가 잘 되어있는 메서드(병합정렬과 삽입 정렬을 함께 사용하는 Timsort 알고리즘 사용)이기 때문에, 상황에 따라 사용하는게 더 좋을 수 있다.
reverse / lambda를 써도 O(NlogN) 만큼 소요
# O(NlogN + N + N) -> O(NlogN)
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
mapped = {}
result = []
# O(NlogN)
# nums를 정렬
temp = sorted(nums)
# O(N)
# 현 인덱스가 현 요소 값보다 작은 요소의 갯수이다.
# if문을 통해, 같은 숫자는 제외하도록 설정하였다.
for i in range(len(nums)):
if temp[i] not in mapped:
mapped[temp[i]] = i
# O(N)
# mapped에 작성된 내용을 nums 순서대로 다시 가져온다.
for i in nums:
result.append(mapped[i])
return result
Python
복사