6.7 6.7

main.py

"""
# 문제 : 3번째 큰 수

- 배열에서 3번재로 큰 수를 찾아서 반환하도록 하자.
- 만약 3번째로 큰 수가 없다면 가장 큰 수를 반환하면 된다. 예를 들어서 배열에 [1, 2, 3] 이 있다면 1을 반환하고
3번째가 없는 배열 [2, 3] 이라면 3을 반환하면 된다.

### 아이디어 (정렬)

1. 배열을 역순으로 정렬한다.
2. 가장 큰수를 변수에 저장한다.
3. 배열을 순회한다.
  - 해시 테이블을 이용하여, 중복된 숫자는 다음으로 넘어간다.
  - 중복된 숫자를 제외하고 3번째 숫자라면 순회를 종료한다.
  - 순회 과정에서 중복된 숫자를 제외하고 3번째 숫자를 찾지 못했다면, 2번에서 저장한 가장 큰 수가 저장된다.

시간 복잡도 : O(nlogn)
공간 복잡도 : O(n)

### 아이디어 (우선 순위 큐)

1. 우선 순위 큐(최대 힙 사용)를 생성한다.
2. 각 요소를 순회 하면서 중복을 제외하고 최대 힙을 구성한다.
3. 최대 힙 내에 요소가 2개 이하라면, 맨 앞에 있는 숫자를 반환한다.
4. 최대 힙 내에 요소가 3개 이상이라면, 힙에서 3번 요소를 꺼내서 3번째 요소를 반환 한다.

시간 복잡도 O(nlogn)
공간 복잡도 O(n)
"""
import heapq
from typing import List


def solution(nums: List[int]) -> int:
    cnt = 0
    thrid_max = 0

    check_dup = set()

    nums.sort(reverse=True)
    third_max = nums[0]

    for num in nums:
        if num in check_dup:
            continue
        check_dup.add(num)

        if cnt == 2:
            third_max = num
            break
        cnt += 1
    return third_max


def solution2(nums: List[int]) -> int:
    priority_queue = [item * -1 for item in list(dict.fromkeys(nums))]
    heapq.heapify(priority_queue)

    if len(priority_queue) > 2:
        cnt = 2

        while cnt > 0:
            heapq.heappop(priority_queue)
            cnt -= 1
    return priority_queue[0] * -1


if __name__ == "__main__":
    nums = [2, 3, 2, 3, 4, 5, 1, 1, 1]

    print(solution2(nums))