[leetcode] Keep Multiplying Found Values by Two

Keep Multiplying Found Values by Two

처음에 생각한 접근법

리스트를 정렬한 후, 리스트 안에 값이 있으면 original *= 2를 한다. 이렇게 하게 되면 while문에서 O(N)으로 해결이 되지만, "굳이 index가 nums 끝까지 갈 필요가 있을까?"라는 생각이 들었다.

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        nums = sorted(nums)
        index = 0
        
        try:
            index = nums.index(original)
        except:
            return original
        
        while index < len(nums):
            if nums[index] == original:
                original *= 2
            index += 1
        
        return original

다른 사람 풀이

in을 O(1)로 사용하기 위해 set으로 만들어준다. set은 해시 함수와 해시 테이블로 만들어진 자료구조이기 때문에 리스트처럼 처음부터 탐색하는 것이 아니다. 맨 앞에 있는 값이 나 뒤에 있는 값이나 탐색하는 데 걸리는 시간은 똑같이 O(1)이다.

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        numsSet = set(nums)
        
        while original in numsSet:
            original *= 2
        
        return original

기존의 코드처럼 nums을 끝까지 탐색하는 것이 아니라서 시간이 단축되었다.

참고 자료

• Programming Live with Larry
• set에서 in의 성능