[리트코드] 3870 - Count Commas in Range

3870. Count Commas in Range

Easy

---

You are given an integer n.

Return the total number of commas used when writing all integers from [1, n] (inclusive) in standard number formatting.

In standard formatting:

• A comma is inserted after every three digits from the right.
• Numbers with fewer than 4 digits contain no commas.

 

Example 1:

Example 2:

 

Constraints:

• 1 <= n <= 105

분류

수학

---

문제 풀이

주어진 코드는 1부터 n까지의 모든 정수를 표준 숫자 서식으로 표기했을 때 사용되는 총 쉼표의 개수를 계산하는 문제입니다.

---

문제 분석

이 문제는 정수 n이 주어졌을 때, 1부터 n까지의 모든 숫자를 표준 서식에 따라 작성할 때 사용되는 총 쉼표의 개수를 반환하는 것을 목표로 합니다. 표준 서식 규칙은 다음과 같습니다:

• 오른쪽에서 세 자리마다 쉼표가 삽입됩니다.
• 4자리 미만의 숫자에는 쉼표가 없습니다. 예를 들어, "1,000", "1,001", "1,002"는 각각 1개의 쉼표를 가지며, 총 3개의 쉼표가 사용됩니다. 입력 n의 범위는 1 <= n <= 10^5입니다. 이 범위에서는 어떤 숫자도 2개 이상의 쉼표를 가질 수 없습니다 (예: 1,000,000은 2개의 쉼표를 가지지만, n은 100,000까지만 가능). 따라서, 1000 이상 n 이하의 숫자들은 각각 1개의 쉼표를 가집니다.

접근 방법

문제의 핵심은 각 숫자가 가지는 쉼표의 개수를 단순히 합산하는 것입니다. 숫자가 1000 미만이면 쉼표가 없고, 1000 이상이면 첫 번째 쉼표가 생깁니다. 1,000,000 이상이면 두 번째 쉼표가 생기고, 1,000,000,000 이상이면 세 번째 쉼표가 생기는 식입니다.

제약 조건 n <= 10^5를 고려하면, 숫자는 최대 1개의 쉼표만 가질 수 있습니다 (예: 100,000). 따라서, 1000부터 n까지의 모든 숫자는 각각 1개의 쉼표를 가지게 됩니다. 코드의 접근 방식은 이 아이디어를 더욱 일반화한 것입니다. 각 '쉼표 자리' (천의 자리, 백만의 자리, 십억의 자리 등)를 기준으로, 해당 쉼표를 가지는 숫자가 몇 개인지 세는 방식입니다.

• 첫 번째 쉼표 (1천 단위): 1000 이상의 모든 숫자들은 첫 번째 쉼표를 가집니다.
• 두 번째 쉼표 (1백만 단위): 1,000,000 이상의 모든 숫자들은 두 번째 쉼표를 가집니다.
• 세 번째 쉼표 (10억 단위): 1,000,000,000 이상의 모든 숫자들은 세 번째 쉼표를 가집니다. 이처럼 각 쉼표 자리에 대해 쉼표를 가지는 숫자의 개수를 세어 모두 더하면 총 쉼표의 개수가 됩니다.

구현 설명

1. 결과값 및 기준값 초기화

• answer = 0: 최종적으로 반환할 총 쉼표의 개수를 저장할 변수를 0으로 초기화합니다.
• check = 1000: 첫 번째 쉼표가 등장하기 시작하는 최소 숫자(1,000)를 나타내는 기준값을 check 변수에 저장합니다. 이 check 값은 1천 단위, 1백만 단위, 10억 단위 등 쉼표가 생기는 기준 숫자를 의미합니다.

2. 각 쉼표 자리에 대한 개수 누적 계산

• while check <= n:: check 값이 n보다 작거나 같은 동안 반복합니다. 이 루프는 1천의 자리, 1백만의 자리 등 각 쉼표 위치에 해당하는 쉼표의 개수를 순차적으로 계산하여 answer에 누적합니다.
  • answer += (n - check + 1): 현재 check 값부터 n까지의 모든 숫자는 현재 check가 나타내는 자리에 쉼표를 가집니다. 예를 들어, check가 1000일 때 n이 1002라면, 1000, 1001, 1002는 모두 첫 번째 쉼표를 가집니다. 이들의 개수는 n - check + 1 (즉, 1002 - 1000 + 1 = 3)이 됩니다. 이 개수를 answer에 더하여 총 쉼표 개수에 누적합니다.
  • check *= 1000: 다음 쉼표 위치의 기준값을 계산하기 위해 check를 1000배 증가시킵니다. (예: 1000 -> 1,000,000 -> 1,000,000,000).

3. 최종 결과 반환

• return answer: while 루프가 종료되면 answer에 저장된 총 쉼표의 개수를 반환합니다. n의 제약 조건(10^5) 때문에 이 루프는 check가 1000일 때 최대 한 번만 실행되거나(n >= 1000), 한 번도 실행되지 않을 수 있습니다(n < 1000).

⏱복잡도 분석

• 시간 복잡도 (Time Complexity): O(log N)

  • check 변수는 각 반복마다 1000배씩 증가합니다 (check *= 1000).
  • 루프는 check가 n보다 커질 때까지 실행되므로, 루프의 반복 횟수는 log_1000(N)에 비례합니다.
  • 이는 log(N)에 비례하는 시간 복잡도를 의미합니다.
  • 주어진 n의 제약 조건 1 <= n <= 10^5 하에서는 check가 1000에서 시작하여 1,000,000이 되기 때문에 루프는 최대 1번만 실행됩니다 (n < 1000이면 0번, 1000 <= n <= 10^5이면 1번). 따라서 이 특정 문제의 제약 하에서는 상수 시간인 O(1)에 가깝게 동작하지만, 일반적인 N에 대한 확장성을 고려하면 O(log N)으로 표현하는 것이 더 정확합니다.

• 공간 복잡도 (Space Complexity): O(1)

  • answer, check와 같이 몇 개의 변수만을 사용하며, 입력 크기 n에 비례하여 추가적인 메모리를 사용하지 않습니다. 따라서 상수 공간 복잡도 O(1)을 가집니다.

핵심 포인트

1. 쉼표 발생 기준: 쉼표는 숫자의 오른쪽에서 세 자리마다 삽입되므로, 10^3 (1,000), 10^6 (1,000,000), 10^9 (1,000,000,000) 등 1000의 거듭제곱을 기준으로 새로운 쉼표 자리가 나타납니다.
2. 누적 합산 로직: 각 쉼표 위치(check 값)에 대해, check부터 n까지의 모든 숫자가 해당 위치에 쉼표를 가진다고 가정하고 그 개수(n - check + 1)를 answer에 더합니다. 이렇게 하면 각 쉼표 위치가 전체 쉼표 개수에 기여하는 바를 효율적으로 합산할 수 있습니다.
3. 일반화된 풀이: n의 제한이 10^5로 비교적 작지만, 이 코드는 n이 훨씬 큰 값(예: 10^12)으로 주어지더라도 효율적으로 동작하도록 설계된 일반적인 풀이입니다. check를 1000배씩 증가시키는 while 루프 구조가 이를 가능하게 합니다.

풀이 코드

class Solution:
    def countCommas(self, n: int) -> int:
        answer = 0
        check = 1000

        while check <= n:
            answer += (n - check + 1)
            check *= 1000

        return answer



#1,000
#1,000,000
#1,000,000,000