1. 문제 소개

2154. Keep Multiplying Found Values by Two

2. 나의 풀이

풀이 자체는 쉬웠으나 빠르게 푸는 방법을 고민해야하는 문제였다.
nums를 정렬하고 전체 배열을 한 번만 순회하는 방향으로 풀었고, 시간복잡도는 정렬로 인해 $O(n \,log n)$이다.

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        now = original           # 현재 검사할 값(초기값은 original)
        nums.sort()              # nums를 정렬해 작은 값부터 순서대로 비교
        
        for num in nums:         # 정렬된 nums를 순회하며
            if num == now:       # 현재 값 now가 nums 안에 존재하는 경우
                now *= 2         # 규칙에 따라 now를 두 배로 증가시킴
        
        return now if now != original else original
        # now가 한 번이라도 업데이트되었다면 최종 now 반환
        # 업데이트가 없으면 original 그대로 반환

3. 다른 풀이

집합으로 바꿔 풀 수도 있고, 이 경우 시간복잡도는 $O(n)$이다.

class Solution:
    def findFinalValue(self, nums: List[int], original: int) -> int:
        s = set(nums)             # nums를 set으로 변환하여 O(1)에 검사 가능하게 함
        
        while original in s:      # original 값이 집합 안에 존재하는 동안 반복
            original *= 2         # 규칙에 따라 값을 즉시 두 배로 증가시킴
        
        return original           # 더 이상 집합에 존재하지 않는 시점의 값을 반환

4. 결론

이렇게 여러 방향으로 생각할 수 있는 문제가 좋다.