[2024] day 149. leetcode 1608. Special Array With X Elements Greater Than or Equal X

gunny·2024년 5월 28일

leetcode 1608. Special Array With X Elements Greater Than or Equal X leetcode 1608. Special Array With X Elements Greater Than or Equal X python

코딩테스트

목록 보기

463/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 27일 (월)
Leetcode daily problem

1608. Special Array With X Elements Greater Than or Equal X

https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x/?envType=daily-question&envId=2024-05-27

Problem

음수가 아닌 정수로 구성된 배열 nums가 제공 될 때, x보다 크거나 같은 요소의 개수가 정확히 "x" 여야 한다. nums에 정확히 x개의 숫자가 있는 숫자 x가 존재하는 경우 "unique" 한 것으로 간주한다.
여기서 x가 nums의 요소일 필요는 없다.

배열이 "unique" 하면 x를 반환하고, 그렇지 않으면 -1을 반환한다. nums가 "unique" 하면 x의 값도 고유하.

즉, 주어진 정수 배열 nums가 주어질 때 배열 nums에서 x보다 크거나 같은 요소의 개수가 정확히 'x'인 특수한 값 'x'를 찾는다. 존재하면 해당 값을 반환하고 그렇지 않으면 -1을 반환한다. ㅂ

Solution

Counting Sort + Prefix Sum

1에서 N까지 가능한 모든 값보다 크거나 같은 배열 nums의 정수 수를 찾아 전체 시간 복잡도를 줄일 수 있다.

각 정수의 빈도를 freq 배열에 저장하면 각 정수보다 크거나 같은 정수의 개수를 효율적으로 찾을 수 있다다. 그리고 x에 대해 가능한 값 범위의 끝(즉, N에서 1까지)에서 접두어 합계를 통해서 현재 요소보다 큰 배열 값의 수를 계산하기 위해 freq의 오른쪽 끝에서 정수의 빈도를 계속 추가한다.

접두사 합계(정확하게 말하면 접미사, 오른쪽 끝부터 계산하므로)는 별도의 배열일 필요가 없는데, 누적 합계를 계산하고 현재 합계가 현재 값과 같은지 확인하면 된다. 오른쪽 끝의 현재 합계가 현재 값과 같으면 현재 값을 반환하고, 그렇지 않으면 계속 반복한다. 루프가 완료된 후 유효한 x를 찾지 못하면 -1을 반환한다.

모든 값이 0인 N + 1 크기의 배열을 초기화한다. 그 후에 주어진 배열을 탐색하면서 각 정수의 빈도를 freq 배열에 저장한다. nums[i] 값이 N보다 크면 빈도를 인덱스 N에 저장한다.

현재 요소보다 크거나 같은 요소의 수를 업데이트하기 위해서 처음에 해당 변수를 0으로 초기화하고,

N에서 1까지의 값과 각 값 i에 대해 반복하면서
현재 요소보다 크거나 같은 요소의 수의 freq[i] 값을 추가한다.

i 값이 해당 변수와 같으면 i를 반환하고, 아니면
-1을 반환한다.

Code

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        n = len(nums)
        freq = [0] * (n+1)
        for num in nums:
            freq[min(n, num)] +=1
            
        
        num_equal = 0
        
        for i in range(n, 0, -1):
            num_equal += freq[i]
            
            if i == num_equal:
                return i
            
        return -1