[LeetCode] Third Maximum Number

이번에도 Array 문제이고 최대값을 찾는 문제인데

세 번째 최대값을 찾는 것이 특징이다.

 

 

Third Maximum Number

 

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

 

Example 1:

Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.

Example 2:

Input: nums = [1,2]
Output: 2
Explanation:
The first distinct maximum is 2.
The second distinct maximum is 1.
The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

 

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

 

Follow up: Can you find an O(n) solution?

 

 

nums 배열이 주어질 때 세 번째 최대값을 찾으면 된다.

세 번째 최대값이 없을 경우 첫 번째 두 번째 중 최대값을 반환한다.

특이사항은 중복된 원소가 있을 수 있는 점이다.

 

나의 풀이

 

var thirdMax = function(nums) {
    let newNums = [...new Set(nums)];
    
    if(newNums.length > 2) {
        newNums.splice(newNums.indexOf(Math.max(...newNums)), 1);
        newNums.splice(newNums.indexOf(Math.max(...newNums)), 1); 
    }
    
    return Math.max(...newNums);
};

 

우선 중복된 값을 제거하기 위해 Set을 사용했다.

그리고 중복 제거된 배열 newNums의 length 기준으로 3개 이상일 때 아래의 작업을 수행한다.

 

1. 배열 원소 중 max 값을 구한다. (Math.max)

2. max값의 index를 구한다. (indexOf)

3. 해당 인덱스의 값이 제거한다. (splice)

 

그 이후 남아 있는 배열 중 최대값을 return 한다.

 

간단한 문제일 수 있겠지만 생각할 내용이 있었고 풀이도 다양할 것 같았다.

이번에도 눈에 띄는 풀이 2개를 가져왔다.

 

var thirdMax = function(nums) {
    nums = [...new Set(nums)];
    nums.sort((a,b)=>b-a);
    
    if(nums.length <= 2) return nums[0];
    return nums[2];
};

 

첫 번째 풀이는 sort를 사용해서 내림차순으로 정렬 후 3번째 값을 반환한다.

sort를 사용함에도 내 풀이보다 빠른 속도를 보여줬다.

가장 명확하면서도 이해하기 쉬운 풀이었다.

 

var thirdMax = function(nums) {
    const set = new Set(nums)
    
    let max = Math.max(...set) 
    
    if (set.size < 3) {
      return max
    }
  
    set.delete(max)
    max = Math.max(...set)
    set.delete(max)
    return Math.max(...set)
};

 

두 번째 풀이는 내가 생각했던 방법과 비슷하지만 Set을 좀 더 활용한 풀이였다.

속도는 내 풀이와 sort 풀이보다 빠르지만 메모리 사용량이 많은 것이 단점이다.

 

이번에도 간단한 문제였지만 다양한 풀이가 나오는 재밌는 문제를 풀어봤다.

다음에도 재밌는 문제를 찾아서 정리해봐야겠다!