[LeetCode] Find Numbers with Even Number of Digits

목차

문제

• int 배열이 주어졌을 때, 각 원소의 자릿수가 짝수개인 원소의 개수를 구하시오.
• 예시

  • Input: nums = [12,345,2,6,7896]
    Output: 2

  • Input: nums = [555,901,482,1771]
    Output: 1

• 제약조건
  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 105

문제 풀이

풀이 1 : 숫자 추출

• 풀이
  • 7329 = 7*(10^3) + 3*(10^2) + 2*(10^1) + 9*(10^0) 방식으로 분리하여 자릿수를 계산하는 방식으로 문제해결
• 코드

  • class Solution:
        # Helper function to check if the number of digits is even
        def hasEvenDigits(self, num: int) -> bool:
            digit_count = 0
            while num:
                digit_count += 1
                num //= 10
            return digit_count & 1 == 0
    
        def findNumbers(self, nums: List[int]) -> int:
            # Counter to count the number of even digit integers
            even_digit_count = 0
    
            for num in nums:
                if self.hasEvenDigits(num):
                    even_digit_count += 1
    
            return even_digit_count

     
• 시간복잡도 : O(NlogM)
  • 하나의 숫자에 대해서 hasEvenDigits 함수의 시간복잡도 O(logM)가 됩니다. (정확히는 밑이 10인 로그)
    • M은 num 중 가능한 최대 숫자입니다.
  • 모든 숫자에 대해 적용하므로 O(NlogM)입니다.

풀이 2 : 문자열로 변환

• 풀이
  • 숫자를 문자열로 변환한 뒤 len 함수를 통해 길이를 체크하는 방식입니다.
• 코드

  • class Solution:
        def findNumbers(self, nums: List[int]) -> int:
            # Counter to count the number of even digit integers
            even_digit_count = 0
    
            for num in nums:
                # Convert num to string and find its length
                length = len(str(num))
                if length % 2 == 0:
                    even_digit_count += 1
    
            return even_digit_count

• 시간복잡도 : O(NlogM)
  • 하나의 숫자에 str로 변환하는 시간복잡도는 O(logM)입니다. (정확히는 밑이 10인 로그)
    • M은 num 중 가능한 최대 숫자입니다.
  • 길이를 체크하는 len 함수의 시간복잡도는 O(1)입니다.
  • 따라서 모든 숫자에 대해 적용하므로 O(NlogM)입니다.

풀이 3 : 로그 사용

• 풀이
  • 10^k <= x < 10^(k+1)이라고 한다면 k <=log_10(x)<k+1 이 됩니다.
  • 10^k <= x < 10^(k+1)의 자릿수의 개수는 k+1입니다. 예를 들어 4521의 경우 4*10^3+5*10^2+2*10^1+1*10^0 이므로 10^3 보다 크고 10^4보다 작습니다. 여기서 4521의 자릿수의 개수는 4자리입니다.
• 즉, 밑이 10인 로그를 취한 값에 1을 더하면 전체 자릿수가 나오게 됩니다.
• 코드

  • class Solution:
        def findNumbers(self, nums: List[int]) -> int:
            # Counter to count the number of even digit integers
            even_digit_count = 0
    
            for num in nums:
                # Compute the number of digits in num
                digit_count = int(math.floor(math.log10(num))) + 1
                if digit_count % 2 == 0:
                    even_digit_count += 1
    
            return even_digit_count

• 시간복잡도 : O(NlogM)
  • 하나의 숫자에 log를 적용하는 시간 복잡도는 Olog(M)입니다. (정확히는 밑이 10인 로그)
    • M은 num 중 가능한 최대 숫자입니다.
  • math.floor의 경우 버림이므로 O(1)입니다.
  • 따라서 모든 숫자에 대해 적용하므로 O(NlogM)입니다.

풀이 4 : 제약 분석

• 풀이
  • 문제에서 숫자의 범위는 1부터 10^5 까지였습니다. 따라서 단순하게 그냥 x가 1 <=x <10 일 경우 홀수개, 10 <=x <100일 경우, 짝수개, 이런 식으로 나아가게 되면 별다른 함수 실행 없이 O(1)만에 처리가 가능합니다.
• 코드

  • class Solution:
        def findNumbers(self, nums: List[int]) -> int:
            # Counter to count the number of even digit integers
            even_digit_count = 0
    
            for num in nums:
                if (num >= 10 and num <= 99) or (num >= 1000 and num <= 9999) or (num == 100000):
                    even_digit_count += 1
    
            return even_digit_count

• 시간복잡도 : O(N)
  • 제약조건을 잘 이용하면 자릿수가 홀수개인지 짝수개인지 판별하는 것이 O(1)만에 끝나버리게 됩니다.
  • 따라서 전체 숫자에 대한 시간복잡도는 O(N)이 될 것입니다.

알게 된 내용

• 홀수 짝수 비교 시 %2를 이용할 수도 있지만 &1을 이용할 수도 있습니다.
  • 홀수일 경우 이진수로 표현하면 반드시 마지막 숫자는 1일 것입니다.
  • 따라서 홀수&1== 1이 됩니다. 마찬가지로 짝수 &1==0입니다.
• 숫자를 문자로 변환하는 시간복잡도
  • O(logM) (정확히는 밑이 10인 로그)
    • M은 num 중 가능한 최대 숫자입니다.
• log함수의 시간복잡도
  • 숫자 num 1개가 있더라도 log(num)을 하게 되면 이것의 시간복잡도는 O(logM)이 될 것입니다.
    • M은 num 중 가능한 최대 숫자입니다.
    • 아래의 단순화한 log 연산과정만을 보더라도 결국 해당 밑을 계속 제곱하면서 만족하는 로그의 값을 찾아나가는 것입니다. 따라서 math.log 함수의 시간복잡도는 log(num)만큼의 시간이 소요될 것입니다.
  • 단순화한 log 연산과정
    • 문제: 숫자 M에 대한 로그 값을 2의 거듭제곱 형태로 근사하려고 합니다. 즉, 2^x ≈ M인 x 값을 찾으려고 합니다.
    • 단계별 접근:
      • x의 시작 값을 0으로 설정합니다.
      • 2^x가 M보다 작은 동안, x를 1씩 증가시킵니다.
      • 2^x가 M을 초과하거나 같아지면, 그때의 x 값이 M에 대한 로그 값의 근사치입니다.

출처

• https://leetcode.com/explore/learn/card/fun-with-arrays/521/introduction/3237/