12. 숫자의 총 개수 (large : 제한시간 1초) [코드구현력 기르기]

나의 정답1. 시간복잡도 O(n)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char** argv) {

	//freopen("input.txt", "rt", stdin);
	
	int i = 0;
	int n;
	int cnt = 0;
	int comp = 10;
	int increment_size = 1;
	
	scanf("%d", &n);
			
	for(i = 1 ; i <= n ; i++){
		if(i % comp == 0)
		{
			comp *= 10;
			increment_size++;
		}			
		cnt += increment_size;
	}
		
	printf("%d", cnt);
}

// A 65, Z 90
// a 97, z 122

 

나의 정답2. 시간복잡도(log n)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char** argv) {

	//freopen("input.txt", "rt", stdin);
	
	int i = 0;
	int n;
	int temp;
	int sum = 0;
	int digit_num = 0;
	int min_num = 1;
	
	scanf("%d", &n);
	
	temp = n;
	while(temp > 0 ){
		temp /= 10;
		digit_num++;
	}		
			
	for(i = 0 ; i < digit_num - 1 ; i++){
		sum += 9 * min_num * (i + 1);
		min_num *= 10;		
	}
	
	sum += (n - min_num + 1) * digit_num;	
	printf("%d", sum);
}