13. Third Maximum Number

문제

https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3231/

nums 배열에서 세번째로 큰 숫자를 반환하시오.

세번째로 큰 숫자가 없으면 제일 큰 숫자를 반환하시오.

 

내가 생각한 방식

for 루프를 세 번 돌림.

첫번째 루프에서 제일 큰 숫자를 찾고,

두번째 루프에서 두번째로 큰 숫자를,

세번째 루프에서 세번째로 큰 숫자를 찾음.

 

[1, 2]처럼 요소가 3개 미만인 경우 0으로 잘못된 결과 나옴.

int thirdMax(vector<int>& nums) {
    int max1 = 0;
    int max1Index = 0;
    for (int i = 0; i < nums.size(); i++){
        if (nums[i] > max1) {
            // 가장 큰 숫자 찾고 인덱스 저장
            max1 = nums[i];
            max1Index = i;
        }
    }

    int max2 = 0;
    int max2Index = 0;
    for (int i = 0; i < nums.size(); i++){
        if (i != max1Index && nums[i] > max2) {
            // 두번째로 큰 숫자 찾고 인덱스 저장
            max2 = nums[i];
            max2Index = i;
        }
    }

    int max3 = 0;
    for (int i = 0; i < nums.size(); i++){
        if (i != max1Index && i != max2Index && nums[i] > max3) {
            // 세번째로 큰 숫자 찾기
            max3 = nums[i];
        }
    }
    return max3;
}

 

해결방식 1) c++

Leet code 유저 StefanPochmannn

c++의 set 사용.

set : 중복요소 허용 x, 요소 정렬해서 삽입. Binary Search Tree 사용함 => 탐색 시간 복잡도 O(logN)

1) nums 배열 요소를 set top3에 삽입

2) 삽입 후 top3 크기가 4 이상인지 확인

3) 4 이상이면 top3의 첫 요소 삭제 

4) 루프 끝난 후, top3 크기가 3이면 첫 요소 반환. 3보다 작으면 마지막 요소 반환

int thirdMax(vector<int>& nums) {
    set<int> top3;
    for (int i = 0; i < nums.size(); i++) {
        top3.insert(nums[i]);
        if (top3.size() > 3)
            top3.erase(top3.begin());
    }
    # begin()은 첫요소, rbegin()은 마지막 요소 
    return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
}

 

해결방식 2) python

https://leetcode.com/problems/third-maximum-number/discuss/90207/Intuitive-and-Short-Python-solution 

def thirdMax(nums):
  # 1) top3 생성 : 가장 큰 숫자를 내림차순으로 저장할 예정. 무한 음수로 initialize
  top3 = [float('-inf'), float('-inf'), float('-inf')]

  for num in nums:
    if num not in top3:
      if num > top3[0]:
        top3 = [num, top3[0], top3[1]]
      elif num > top3[1]:
        top3 = [top3[0], num, top3[1]]
      elif num > top3[2]:
        top3 = [top3[0], top3[1], num]

  # iterate 이후 3번째로 작은 숫자가 있으면 top3[2]에 저장됨.
  # 3번째로 작은 숫자가 없으면 무한 음수가 남아있음 => 그 중 가장 큰 수 반환
  return max(nums) if float('-inf') in top3 else top3[2]