414. Third Maximum Number

https://leetcode.com/problems/third-maximum-number/

Third Maximum Number - LeetCode

경이롭다

정말 이 문제가 코딩 면접에서 간단하게 물어볼 수 있는 문제라고 생각합니다. 물론 저는 생각해내지 못했지만, 경이로운 해설을 발견했기에 들고 와봤습니다.

 

흑 왜 저는 이런 풀이법을 생각해내지 못할까요.

 

공부를 열심히 합시다.

 

제가 쓴 풀이법입니다. 정말 어디에 내놓기 창피한 풀이법...

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(list(set(nums))) <= 2:
            return max(nums)
        
        return sorted(list(set(nums)))[-3]

사실 이 문제가 라이브러리를 써서 해결하라는 문제가 아니었을겁니다. 고민을 해봤는데, 그래도 해결법이 안나오더라고요.

 

그래서 풀이를 봤는데...

 

와우..

 

이런 풀이법이 !

class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = [-float('inf'), -float('inf'), -float('inf')]
        
        for num in nums:
            if num not in result:
                if num > result[0]:
                    result = [num, result[0], result[1]]
                elif num > result[1]:
                    result = [result[0], num, result[1]]
                elif num > result[2]:
                    result= [result[0], result[1], num]
        
        return result[2] if -float('inf') not in result else max(result)

우선 이 풀이법의 경우 제일 큰 수 3 가지를 기억해놓는다는 것이 키포인트입니다. 그렇게 새로운 큰 수가 들어오면 각자의 분기를 통해 갱신을 해주는 풀이법입니다.

 

사실 간단합니다.

 

마치 콜럼버스의 달걀 세우기 문제처럼 알고나면 너무 쉬운데, 그 아이디어까지 도달하는게 힘든게 문제죠.

 

아마 LeetCode의 Easy 문제는 그 실력을 키워주는 문제들이 많은거 같습니다.

 

Easy라고 쉽게 봤는데, 그러면 안될거 같네요.

---

이상 414. Third Maximum Number였습니다.