<Hard> Number of Digit One (LeetCode : C#)

https://leetcode.com/problems/number-of-digit-one/

📕 문제 설명

정수 n이 주어질 때 n보다 작거나 같은 양의 정수 모두에 대해 1이 들어간 개수 반환하기

• Input
  정수 n
• Output
  n보다 작거나 같은 모든 양의 정수들이 가지는 1의 개수

예제

예를 들어 n = 13이면
n = 1, n = 2, n = 3, .. , n = 10, n = 11, n = 12, n = 13
한자리 수 일 때 1개, 두 자리 수 일 때 5개가 나와서 총 6개를 반환해야한다.

풀이

각 자리수에 대해 계산을 진행한다. 앞의 자리가 1이 아닌 것들은 같은 개수로 처리 되기 때문에 앞 자리가 1인가 아닌가를 기준으로 구현하면 된다.
ex) 100
1의 자리에 있는 1의 개수: 10
10의 자리에 있는 1의 개수: 10
100의 자리에 있는 1의 개수: 1
= 21
ex) 200

1 2 3 4 5.. 
11 ...
.
.
101 102 103 ..
.
.
191 .. 

1의 자리에 있는 1의 개수: 20
10의 자리에 있는 1의 개수: 20
100의 자리에 있는 1의 개수: 100
= 140

public class Solution {
public int CountDigitOne(int n) {
    int ones = 0, m = 1;
    while (m <= n) // 각 digit에 대해 연산 진행 
    {
        int a = n / m, b = n % m; 
        ones += (a + 8) / 10 * m; // 8을 더하는 이유는 앞자리수 2 이상부터는 앞이 1이었던 부분 포함하게 되므로 해당 값 기준 계산 
        if (a % 10 == 1) ones += b + 1; // 앞 자리수가 1인 경우
        m *= 10;
    }

    return ones;
}
}

결과