백준 실버4 1748번(자바)

1748번 문제는 주어진 숫자를 1부터 N까지 나열 했을 때 자릿수가 어떻게 되는지 물어보는 문제다.

해당 문제를 풀면서 문제를 이해하는 것은 빨랐다.

예제를 하나 보면 15가 주어졌을 때 123456789101112131415가 되며 자릿수로 따지면 21이 된다.

이 문제에서 가장 중요한 부분은 그냥 자릿수를 물어본다는 것이다.

나는 그냥 단순하게 String으로 값을 받아 String.length를 출력하게 만들었다. 예제를 입력했을 때 원하는 값이 나왔지만 답을 제출했을 때 메모리 초과가 발생하였다.

여기서 내가 방심한 것은 시간 제한이 0.15초 였던 것과 주어진 데이터 N의 범위가 100,000,000으로 자바 기준으로 시간 복잡도가 O(n)일시 1초가 걸리는 문제였다.

 

 

위의 사진과 같이 처음에 자릿수의 관한 기준점이 필요하다.

만약 i의 값이 10의 자리 기준점인 criteria와 % 연산을 실행했을 경우 0이 나온다면 해당 i 값 부터 10의 자릿수가 된다는 것을 알 수 있다.