Find the Largest Number

Q: 배열에서 최댓값을 찾는 시간 복잡도는 얼마인가요?

한 번 순회하는 데 O(n) 시간이 걸리고 추가 공간은 O(1) 이 필요합니다. 정렬되지 않은 배열에서는 어떤 방법도 이보다 더 나을 수 없습니다. 읽지 않은 원소가 최댓값일 수도 있기 때문입니다. 먼저 정렬하면 O(n log n) 의 비용이 들며, 얻는 이점 없이 더 느립니다.

Q: 누적 최댓값은 왜 0이 아니라 첫 번째 요소에서 시작해야 하나요?

모든 값이 음수라면 그중 0 보다 큰 값은 없으므로 0 에서 시작하는 최댓값은 바뀌지 않고 함수는 0 을 반환합니다. 첫 번째 요소는 항상 실제 후보이므로, 거기서 시작하는 것은 어떤 목록에서든 올바릅니다. 목록이 비어 있지 않다면 해당 언어의 가장 작은 정수를 사용해도 됩니다.

입문배열과 문자열

+10

비어 있지 않은 정수 리스트 nums를 받습니다. 리스트에서 가장 큰 값을 반환하세요. 값은 음수일 수 있으므로 답도 음수일 수 있습니다. max와 같은 내장 최댓값 함수를 사용하지 말고 직접 비교하여 찾으세요.

함수

findMax(nums: integer-array) → integer

numsinteger-array: 검색할 정수 목록
반환값integer: nums에서 가장 큰 값

제약 조건

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

예제

입력: nums = [3, 17, 4, 12, 9]
출력: 17
설명: 왼쪽부터 읽으면, 지금까지 가장 큰 값은 3이고, 그다음은 17입니다. 4, 12, 9 중 어느 것도 17보다 크지 않으므로 답은 17입니다.

입력: nums = [-8, -3, -11, -3]
출력: -3
설명: 모든 값은 음수이고 -3이 0에 가장 가까우므로 가장 큽니다. 두 번 나타나지만, 위치가 아니라 값을 반환합니다.

제출 시 숨은 테스트 +13개

후속 질문

값들을 먼저 쌍으로 비교하면 2n회 대신 약 3n/2회의 비교로 최댓값과 최솟값을 모두 구할 수 있을까요?

힌트

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

3개 중 0개 열림

풀이

건너뛴 값 중 하나가 가장 클 수도 있으므로, 모든 해결 방법은 각 요소를 적어도 한 번씩 읽습니다. 실제로 결정해야 할 것은 현재까지의 최댓값을 어디서 시작하느냐입니다. 최댓값을 첫 번째 요소로 시작하고, 0으로 시작하지 마세요. 목록의 모든 값이 음수일 수도 있기 때문입니다.

복사본을 정렬하고 마지막 값을 가져옵니다

핵심 아이디어

작은 값부터 큰 값 순으로 정렬된 목록에서는 가장 큰 값이 맨 끝에 있습니다. 호출자가 전달한 목록을 그대로 유지하려면 nums를 복사하고, 복사본을 정렬한 다음 마지막 요소를 반환하세요. [3, 17, 4, 12, 9]의 경우 정렬된 복사본은 [3, 4, 9, 12, 17]이고, 마지막 요소는 17입니다.

정답은 맞지만, 정렬은 필요한 것보다 훨씬 많은 작업을 합니다. 모든 값을 순서대로 정렬하는 데 약 n log n번의 비교가 필요합니다. 이는 n = 5000일 때 대략 60,000번으로, 가장 큰 값 하나만 찾으면 되는 경우에도 그렇습니다. 복사본을 만드는 데에도 O(n)의 메모리가 듭니다.

JavaScript와 TypeScript에서는 sort에 비교 함수를 전달하세요. 비교 함수를 전달하지 않으면 숫자를 텍스트로 비교하기 때문에 12와 17이 3보다 앞에 옵니다.

알고리즘

nums를 복사합니다.
숫자를 숫자로 비교하여 복사본을 가장 작은 수부터 가장 큰 수 순으로 정렬합니다.
정렬된 복사본의 마지막 요소를 반환합니다.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

현재 최댓값을 유지하며 한 번 순회하기

핵심 아이디어

지금까지 본 가장 큰 값을 저장할 변수 largest를 하나 둡니다. 이 변수를 nums[0]으로 시작하고, 모든 값과 비교한 뒤 더 큰 값이 나오면 그 값으로 바꿉니다. 반복문이 끝나면 largest는 모든 요소와 비교된 상태이므로, 목록에서 이 값보다 큰 것은 없습니다.

[3, 17, 4, 12, 9]의 경우 largest는 3으로 시작해 17이 되고, 4, 12, 9를 지나도 17을 유지합니다. 이렇게 하면 유용한 비교는 n-1번이고 변수는 하나 더 사용합니다.

nums[0]으로 시작해야 음수로 이루어진 목록도 제대로 처리할 수 있습니다. 대신 0으로 시작하면 [-8, -3, -11, -3]의 어떤 값도 이 값보다 크지 않으므로, 목록에 있지도 않은 값인 0을 반환하게 됩니다.

알고리즘

largest를 nums[0]으로 설정합니다.
nums의 모든 값 x를 반복해서 확인합니다.
x > largest이면 largest를 x로 설정합니다.
반복문이 끝난 후 largest를 반환합니다.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

함정과 경계 사례

반복문은 짧으므로, 실수는 시작값과 읽는 위치에 있습니다.

largest를 0 또는 -1에서 시작하기. 값이 모두 그 시작값보다 작은 목록에서는 목록에 없는 숫자가 반환됩니다.
-1000000 같은 임의로 정한 작은 숫자에서 시작하기. 여기의 값은 -10^9까지 내려가므로, 시작값이 여전히 더 큽니다. nums[0]을 사용하면 추측할 필요가 없습니다.
첫 번째 요소가 nums[1]인 Lua나 R에서 nums[0]을 읽기. Lua는 nil을 반환하고 R은 빈 벡터를 반환합니다.
0부터 시작하는 인덱스를 사용하는 언어에서 i ≤ n으로 반복하여 끝을 넘어선 요소를 읽기.
JavaScript나 TypeScript에서 숫자 비교자를 지정하지 않고 정렬하기. [3, 17, 4, 12, 9]의 문자열 순서에서는 마지막 값이 9이므로 17 대신 9를 반환하게 됩니다.

자주 묻는 질문4

배열에서 최댓값을 찾는 시간 복잡도는 얼마인가요?

한 번 순회하는 데 O(n) 시간이 걸리고 추가 공간은 O(1)이 필요합니다. 정렬되지 않은 배열에서는 어떤 방법도 이보다 더 나을 수 없습니다. 읽지 않은 원소가 최댓값일 수도 있기 때문입니다. 먼저 정렬하면 O(n log n)의 비용이 들며, 얻는 이점 없이 더 느립니다.

max를 사용하지 않고 배열에서 가장 큰 수를 어떻게 찾나요?

첫 번째 요소를 변수에 저장합니다. 나머지 요소를 반복하면서 요소가 변수보다 크면 해당 요소를 대신 저장합니다. 반복이 끝나면 변수에는 가장 큰 값이 들어 있습니다.

누적 최댓값은 왜 0이 아니라 첫 번째 요소에서 시작해야 하나요?

모든 값이 음수라면 그중 0보다 큰 값은 없으므로 0에서 시작하는 최댓값은 바뀌지 않고 함수는 0을 반환합니다. 첫 번째 요소는 항상 실제 후보이므로, 거기서 시작하는 것은 어떤 목록에서든 올바릅니다. 목록이 비어 있지 않다면 해당 언어의 가장 작은 정수를 사용해도 됩니다.

정렬은 가장 큰 값을 찾는 좋은 방법이 언제인가요?

최댓값뿐만 아니라 가장 큰 값 세 개나 중앙값처럼 더 많은 값이 필요하고, 같은 목록에 대해 이런 질문을 여러 번 할 경우입니다. 최댓값 하나만 구할 때는 한 번 순회하는 것이 더 빠르고 목록을 변경하지 않습니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

nums = [3, 17, 4, 12, 9]

기대값