3871. Count Commas in Range II

[zeikar]

Problem link

https://leetcode.com/problems/count-commas-in-range-ii/

Problem Summary

1부터 n까지의 수를 세 자리마다 콤마를 찍어서 쓸 때, 콤마가 총 몇 개 쓰이는지 구하는 문제.

Solution

n이 10^15까지라 하나씩 세는 건 불가능하다.

잘 생각해보면 1000 이상인 수는 콤마가 최소 1개, 10^6 이상이면 최소 2개... 이런 식이다.
즉, 1000의 거듭제곱마다 그 이상인 수의 개수를 더해주면 된다. n 이하에서 div 이상인 수는 n - div + 1개.

10^15까지라 루프는 5번만 돈다. 시간복잡도는 O(log n)

C++로 풀었던 걸 파이썬으로 옮긴 것. C++에서는 오버플로 때문에 unsigned long long을 썼는데 파이썬은 정수 범위 제한이 없어서 그냥 옮기면 된다.

Source Code

class Solution:
    def countCommas(self, n: int) -> int:
        res = 0
        div = 1000
        while n >= div:
            res += n - div + 1
            div *= 1000

        return res