Second Largest Number

Q: 두 번째로 큰 요소를 찾는 시간 복잡도는 얼마인가요?

1회 통과 방식과 2회 통과 방식은 모두 O(n) 시간이 걸리고 추가 공간은 O(1) 이 필요합니다. 먼저 정렬하면 O(n log n) 시간이 걸립니다. 모든 값을 적어도 한 번은 읽어야 하므로 O(n) 보다 더 빠를 수는 없습니다.

Q: 중복 항목은 두 번째로 큰 요소에 어떤 영향을 미치나요?

이 문제는 두 번째로 큰 고유한 값을 묻기 때문에 최댓값의 중복 항목은 건너뜁니다. [9, 9, 7] 의 경우 답은 7 입니다. 문제의 일부 버전에서는 위치를 기준으로 세어 9 를 답으로 제시하므로, 코드를 작성하기 전에 어떤 의미인지 확인하세요.

Q: 두 번째로 큰 값이 없을 때는 무엇을 반환해야 하나요?

여기서는 그런 일이 일어날 수 없습니다. 목록에는 항상 서로 다른 두 값이 들어 있습니다. 일반적으로 [4, 4, 4] 와 같은 목록에는 답이 없으므로 -1 이나 null 과 같은 표시값을 반환하거나 오류를 발생시킵니다. 반복문이 끝난 후에도 second 가 여전히 시작 값이라면 이 경우를 감지할 수 있습니다.

입문배열과 문자열

+10

정수 목록 nums가 주어집니다. 두 번째로 큰 서로 다른 값을 반환하세요. 즉, 최댓값보다 엄격히 작은 값 중 가장 큰 값입니다. 값은 중복될 수 있으므로 [5, 5, 3]의 답은 5가 아니라 3입니다. 목록에는 항상 서로 다른 값이 두 개 이상 있습니다.

함수

secondLargest(nums: integer-array) → integer

numsinteger-array: 서로 다른 값이 두 개 이상 포함된 정수 목록
반환값integer: 최댓값보다 작은 값 중 가장 큰 값

제약 조건

2 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums에는 서로 다른 값이 두 개 이상 포함되어 있습니다.

예제

입력: nums = [4, 9, 2, 7, 9]
출력: 7
설명: 최댓값은 9입니다. 두 번 나타나지만 최댓값이 두 번째로 나온 것은 계산하지 않으므로, 그다음으로 큰 값인 7이 답입니다.

입력: nums = [-5, -1, -8]
출력: -5
설명: 값은 큰 것부터 작은 것 순으로 -1, -5, -8입니다. 두 번째로 큰 값은 음수이지만 -5입니다.

입력: nums = [6, 6, 6, 3]
출력: 3
설명: 서로 다른 값은 6과 3, 두 개뿐입니다. 6이 몇 번 반복되든 두 번째로 큰 값은 3입니다.

제출 시 숨은 테스트 +15개

후속 질문

한 번의 순회로 변수 세 개를 사용하고 정렬 없이 세 번째로 큰 고유한 값을 반환할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

두 가지 점 때문에 최댓값을 찾는 것보다 어렵습니다. 최댓값은 반복될 수 있으며, 반복된 값은 두 번째로 큰 값으로 보고하면 안 됩니다. 답은 음수일 수 있으므로 0에서 시작하는 변수는 모든 항목이 음수인 목록에서 잘못된 답을 냅니다. 엄격한 비교를 사용해 한 번의 순회로 서로 다른 상위 두 값을 추적하면 두 가지 문제를 모두 해결할 수 있습니다.

정렬하고 최댓값을 지나 한 단계 내려가세요

핵심 아이디어

복사본을 오름차순으로 정렬합니다. 최댓값은 맨 끝에 있으며, 연속해서 여러 번 나올 수도 있습니다. 끝에서 왼쪽으로 이동하며 최댓값의 모든 복사본을 지나가면, 처음 만나는 다른 값이 두 번째로 큰 값입니다. [6, 6, 6, 3]의 경우 정렬된 복사본은 [3, 6, 6, 6]입니다. 6 세 개를 건너뛰고 3에 도달합니다.

여기서 마지막에서 두 번째 요소를 반환하는 것이 흔히 하는 실수입니다. [4, 9, 2, 7, 9]의 경우 다시 최댓값인 9를 반환합니다. 목록에는 서로 다른 값이 적어도 두 개 있으므로, 이동 중 목록의 맨 앞을 벗어나는 일은 없습니다.

정답은 맞지만, 가장 큰 두 값만 신경 쓰면 되는데도 정렬은 모든 값을 정렬합니다. 시간은 O(n log n)이 들고, 복사본에는 O(n)의 메모리가 필요합니다.

알고리즘

nums를 복사하고, 복사본을 가장 작은 값부터 가장 큰 값 순으로 정렬합니다.
인덱스 i를 마지막 위치에서 시작합니다.
i에 있는 값이 최댓값과 같으면 i를 왼쪽으로 한 칸 이동합니다.
i에 있는 값을 반환합니다.

def secondLargest(nums):
    ordered = sorted(nums)
    i = len(ordered) - 1
    # Step left past every copy of the maximum.
    while ordered[i] == ordered[-1]:
        i -= 1
    return ordered[i]

두 번의 패스

핵심 아이디어

작업을 두 단계로 나눕니다. 첫 번째 단계에서는 가장 큰 수 찾기에서처럼 최댓값을 찾습니다. 두 번째 단계에서는 그 최댓값보다 엄격히 작은 값 중 가장 큰 값을 찾습니다. [4, 9, 2, 7, 9]의 경우 첫 번째 단계에서 9를 찾고, 두 번째 단계에서는 두 9를 모두 건너뛴 뒤 4, 2, 7 중 가장 큰 값인 7을 유지합니다.

second는 목록에 들어갈 수 있는 모든 값보다 작은 값으로 시작합니다. 예를 들어 언어에서 가장 작은 정수로 시작할 수 있습니다. 목록에는 서로 다른 값이 적어도 두 개 있으므로, 최댓값보다 작은 값이 존재하며 항상 시작값을 대체합니다.

각 단계는 실행 중인 최댓값을 구하므로 전체 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)입니다. 단점은 목록을 두 번 읽어야 한다는 것입니다. 값이 하나씩 도착하고 읽은 뒤 사라지는 경우에는 불가능합니다.

알고리즘

nums를 한 번 순회하며 최댓값을 largest에 저장합니다.
second를 허용되는 모든 값보다 작은 값으로 설정합니다.
다시 순회합니다. x < largest이고 x > second인 각 x에 대해 second를 x로 설정합니다.
second를 반환합니다.

def secondLargest(nums):
    largest = nums[0]
    for x in nums:
        if x > largest:
            largest = x
    second = float("-inf")  # below every allowed value
    for x in nums:
        if x < largest and x > second:
            second = x
    return second

상위 두 개를 한 번에 추적하기

핵심 아이디어

지금까지 본 상위 두 개의 서로 다른 값을 저장할 largest와 second 변수를 유지합니다. 새 값 x는 세 가지 경우 중 하나에 해당합니다. x가 largest보다 크면 기존 largest가 두 번째 자리로 내려가고 x가 가장 큰 값이 됩니다. x가 second와 largest 사이에 엄격히 놓이면 새로운 second가 됩니다. 그 밖의 경우에는 아무것도 바뀌지 않습니다.

중복을 처리하는 것은 엄격한 비교입니다. [4, 9, 2, 7, 9]의 경우 largest는 4가 된 다음, second = 4인 상태에서 9가 됩니다. 2는 아무것도 바꾸지 않고, 7은 4와 9 사이에 있으므로 second = 7이 됩니다. 마지막 9는 largest와 같으므로 건너뜁니다. 답은 7입니다.

두 변수를 모두 가능한 모든 값보다 작은 값으로 시작하세요. 둘 다 0으로 시작하면, 어떤 값도 0보다 커지지 않으므로 [-5, -1, -8]에 대해 0을 반환합니다. 목록에는 서로 다른 값 두 개가 있으므로 second는 항상 목록에 실제로 있는 값으로 끝납니다.

알고리즘

largest와 second를 허용되는 모든 값보다 작게 설정합니다.
nums의 모든 값 x를 순회합니다.
x > largest이면 largest를 second로 옮기고 largest를 x로 설정합니다.
그렇지 않고 x < largest와 x > second가 모두 참이면 second를 x로 설정합니다.
반복문이 끝난 후 second를 반환합니다.

def secondLargest(nums):
    # Both start below every allowed value.
    largest = second = float("-inf")
    for x in nums:
        if x > largest:
            second = largest  # the old maximum drops to second place
            largest = x
        elif largest > x > second:
            second = x
    return second

함정과 경계 사례

잘못된 답은 대부분 최댓값이 중복되거나 음수 값이 있을 때 나옵니다.

정렬된 목록의 끝에서 두 번째 요소를 반환하는 경우입니다. [4, 9, 2, 7, 9]처럼 최댓값이 중복되면, 그 값도 다시 최댓값입니다.
변수를 0으로 시작하는 경우입니다. [-5, -1, -8]에서는 0보다 큰 값이 없으므로 목록에 없는 숫자 0을 반환합니다.
첫 번째 조건에서 x >= largest를 작성하는 경우입니다. 그러면 두 번째 9가 첫 번째 9를 second에 넣고, 결국 9를 반환합니다.
새로운 최댓값이 나타날 때만 second를 업데이트하는 경우입니다. [10, 20, 15]에서는 15가 second에 들어가지 않아 10을 반환합니다.
집합으로 중복을 제거한 다음 정렬하는 경우입니다. 작동은 하지만, 한 번의 순회로 처리할 수 있는 작업에 O(n)의 메모리와 O(n log n)의 시간이 듭니다.

자주 묻는 질문4

배열에서 두 번째로 큰 숫자를 한 번의 순회로 어떻게 찾나요?

지금까지 확인한 값 중 가장 큰 값과 두 번째로 큰 서로 다른 값을 유지합니다. 어떤 값이 가장 큰 값보다 크면 기존의 가장 큰 값이 두 번째 자리로 이동합니다. 어떤 값이 두 값 사이에 엄격히 놓이면 두 번째 값을 대체합니다. 한 번 순회한 후에는 두 번째 변수에 답이 저장됩니다.

두 번째로 큰 요소를 찾는 시간 복잡도는 얼마인가요?

1회 통과 방식과 2회 통과 방식은 모두 O(n) 시간이 걸리고 추가 공간은 O(1)이 필요합니다. 먼저 정렬하면 O(n log n) 시간이 걸립니다. 모든 값을 적어도 한 번은 읽어야 하므로 O(n)보다 더 빠를 수는 없습니다.

중복 항목은 두 번째로 큰 요소에 어떤 영향을 미치나요?

이 문제는 두 번째로 큰 고유한 값을 묻기 때문에 최댓값의 중복 항목은 건너뜁니다. [9, 9, 7]의 경우 답은 7입니다. 문제의 일부 버전에서는 위치를 기준으로 세어 9를 답으로 제시하므로, 코드를 작성하기 전에 어떤 의미인지 확인하세요.

두 번째로 큰 값이 없을 때는 무엇을 반환해야 하나요?

여기서는 그런 일이 일어날 수 없습니다. 목록에는 항상 서로 다른 두 값이 들어 있습니다. 일반적으로 [4, 4, 4]와 같은 목록에는 답이 없으므로 -1이나 null과 같은 표시값을 반환하거나 오류를 발생시킵니다. 반복문이 끝난 후에도 second가 여전히 시작 값이라면 이 경우를 감지할 수 있습니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

nums = [4, 9, 2, 7, 9]

기대값

Second Largest Number

함수

제약 조건

예제

힌트

풀이

정렬하고 최댓값을 지나 한 단계 내려가세요

두 번의 패스

상위 두 개를 한 번에 추적하기

함정과 경계 사례

자주 묻는 질문4

비슷한 문제