Leaders in an Array

Q: 같은 값도 리더로 간주되나요?

여기서는 그렇습니다. 리더는 오른쪽에 있는 모든 요소보다 크거나 같아야 하므로, [4, 7, 7, 1, 7] 에서는 7 세 개가 모두 리더입니다. 일부 버전에서는 엄격히 더 커야 한다고 요구합니다. 이때는 > 로 비교하며, 값이 같은 요소 중 마지막 요소만 리더가 됩니다.

쉬움배열과 문자열

+10

정수 배열 nums가 주어집니다. 원소가 오른쪽에 있는 모든 원소보다 크거나 같으면 해당 원소는 리더입니다. 마지막 원소의 오른쪽에는 아무것도 없으므로 항상 리더입니다. nums에서 왼쪽에서 오른쪽으로 나타나는 순서대로 모든 리더를 반환하세요.

함수

leaders(nums: integer-array) → integer-array

numsinteger-array: 검색할 정수 배열
반환값integer-array: 왼쪽에서 오른쪽으로 본 nums의 선두 요소

제약 조건

1 ≤ nums.length ≤ 25000
-10⁹ ≤ nums[i] ≤ 10⁹

예제

입력: nums = [12, 5, 9, 3, 6, 2]
출력: [12, 9, 6, 2]
설명: 2가 마지막에 있으므로 선두에 옵니다. 6은 그 뒤에 있는 2를 이기고, 9는 3, 6, 2를 이기며, 12는 모든 수를 이깁니다. 5는 9에게 지고 3은 6에게 지므로 답은 [12, 9, 6, 2]입니다.

후속 질문

값이 한 번에 하나씩 들어오고 각 값이 들어온 후 지금까지의 리더를 보고해야 한다면, 값마다 분할 상환 O(1) 시간으로 목록을 어떻게 업데이트하나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

왼쪽부터 읽으면 각 요소마다 접미사를 새로 확인해야 합니다. 대신 오른쪽부터 살펴보세요. 접미사에 대해 알아야 할 것은 최댓값뿐이며, 변수 하나에 이를 저장하면 됩니다. 이렇게 하면 O(n²) 확인 작업을 한 번의 순회로 바꿀 수 있습니다.

오른쪽의 모든 항목을 확인하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

정의를 적용하세요. 각 인덱스 i에 대해 뒤에 오는 요소들을 훑다가 nums[i]보다 엄격히 큰 첫 번째 요소에서 멈춥니다. 끝까지 훑었는데도 그런 요소가 없으면 nums[i]가 선두입니다. 인덱스를 왼쪽에서 오른쪽으로 검사하므로 선두 요소들도 순서대로 나옵니다. [12, 5, 9, 3, 6, 2]에서는 5는 9에서 멈추고 3은 6에서 멈춥니다.

비용은 끝까지 이어지는 탐색에 있습니다. 같은 값 24,999개 뒤에 더 큰 값 하나가 오면, 각 요소가 배열을 거의 끝까지 훑습니다. 약 25,000 × 25,000 / 2, 즉 3 × 10^8회를 초과하는 비교가 이루어집니다.

알고리즘

빈 결과 목록을 만듭니다.
각 인덱스 i에 대해 j를 i + 1부터 끝까지 살펴봅니다.
어떤 nums[j]가 nums[i]보다 크면 중단합니다. nums[i]는 리더가 아닙니다.
그러한 j가 없으면 nums[i]를 결과에 추가합니다.
결과를 반환합니다.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

오른쪽에서 누적 최댓값을 구하며 한 번 순회하기

핵심 아이디어

오른쪽의 모든 요소보다 크거나 같은 것은 그 요소들의 최댓값보다 크거나 같은 것과 같습니다. 오른쪽에서 왼쪽으로 이동하면서 그 최댓값을 계속 갱신할 수 있습니다. 마지막 요소가 선두가 되어 최댓값으로 시작합니다. 왼쪽에 있는 각 요소는 최댓값보다 크거나 같으면 선두가 되고, 새로운 최댓값이 됩니다. 그렇지 않으면 그 오른쪽에 더 큰 값이 있습니다.

[12, 5, 9, 3, 6, 2]에서는 2가 선두가 되고, 이어서 6, 9, 12가 선두가 되며, 3과 5는 최댓값보다 작습니다. [2, 6, 9, 12]를 찾았고, 이를 뒤집으면 정답입니다.

각 요소는 한 번씩 비교됩니다. 결과를 제외하면 시간은 O(n), 추가 공간은 O(1)입니다. R 버전은 logical(n) 벡터에 선두 요소를 표시하므로 추가 공간은 O(n)입니다.

알고리즘

결과의 마지막 요소로 추가하고 best를 해당 값으로 설정합니다.
i를 끝에서 두 번째 인덱스부터 0까지 감소시킵니다.
nums[i] ≥ best이면 nums[i]를 결과에 추가하고 best를 해당 값으로 설정합니다.
리더가 왼쪽에서 오른쪽으로 읽히도록 결과를 뒤집고 반환합니다.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

함정과 경계 사례

지금까지의 최댓값과 비교할 때 ≥ 대신 >를 사용하는 경우. [4, 7, 7, 1, 7]에서는 모든 7이 리더이지만, 엄격한 비교를 사용하면 마지막 7만 남습니다.
최댓값을 마지막 요소가 아니라 0으로 설정하는 경우. [-1, -5]에서는 두 요소를 모두 반환해야 하지만, 최댓값이 0이면 둘 다 제외됩니다.
리더를 찾은 순서대로 반환하는 경우. [12, 9, 6, 2]가 아니라 [2, 6, 9, 12]가 됩니다.
마지막 요소를 결과에 이미 넣은 뒤, 루프를 마지막 인덱스에서 시작해 마지막 요소를 두 번 추가하는 경우.
각 요소를 이웃 요소와만 비교하는 경우. [5, 3, 9]에서 5는 옆에 있는 3보다 크지만, 9가 있으므로 정답은 [9]입니다.

자주 묻는 질문3

배열에서 리더를 찾는 시간 복잡도는 무엇인가요?

오른쪽에서 한 번만 순회하면 O(n)입니다. 각 요소를 현재까지의 최댓값과 한 번씩 비교하기 때문입니다. 각 요소를 오른쪽의 모든 요소와 비교하면 최악의 경우 O(n²)의 비용이 들며, 예를 들어 모든 값이 같은 경우가 그렇습니다.

마지막 요소는 항상 선두 요소인가요?

네. 리더는 오른쪽에 있는 모든 요소보다 크거나 같아야 하며, 마지막 요소의 오른쪽에는 요소가 없으므로 확인할 것이 없어 조건이 성립합니다.

같은 값도 리더로 간주되나요?

여기서는 그렇습니다. 리더는 오른쪽에 있는 모든 요소보다 크거나 같아야 하므로, [4, 7, 7, 1, 7]에서는 7 세 개가 모두 리더입니다. 일부 버전에서는 엄격히 더 커야 한다고 요구합니다. 이때는 >로 비교하며, 값이 같은 요소 중 마지막 요소만 리더가 됩니다.

def leaders(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [12, 5, 9, 3, 6, 2]

예상 출력

[12, 9, 6, 2]