자릿수 찾기

오늘 우리는 기본적인 DSA 문제를 살펴볼 것입니다.

Find the number of digits for the given number

이 문제를 다른 방식으로 해결할 수 있는 방법을 살펴보겠습니다.

우리는 프로그램에 주어진 모든 입력이 0보다 크고 단순화를 위해 선행 0이 없다고 가정합니다.

선행 0이 있는 숫자의 경우 나중에 볼 수 있는 다른 기술이 있습니다.

우리는 다음과 같은 방법으로 문제를 해결할 것입니다.

반복 방법

재귀 방법

Log10 방법 사용

가장 일반적인 솔루션인 반복 방법을 살펴보겠습니다.

public int countByIteration(int number) {
    int count = 0;
    while (number > 0) {
      ++count;
      number = number / 10;
    }
    return count;
  }

주어진 입력이 123이라고 생각하면 3자리가 있습니다.
자릿수를 저장하기 위해 변수 개수를 초기화합니다.int count =0;
주어진 숫자가 0보다 큰지 확인하는 while 루프를 만들었습니다.
while(number>0){}
123은 0보다 크므로 while 루프 내부로 들어갑니다.

while 루프 내에서 숫자(123)가 0(현재 count=1)이 아니기 때문에 카운트 값을 증가시킵니다.

NOTE:- when you divide 2 integers in java 12/10 its 1 not 1.2(result is int), when you divide 2 double in java 12.00/10.00 its 1.2
not 1(result is double) and if you divide one integer and one double 12.00/10 its 1.2(result is double)

숫자(123)를 10으로 나누면 123이 12가 됩니다.

이제 while 루프는 0보다 12가 큰지 확인합니다. 12가 0보다 크기 때문에 다시 while 루프에 들어가 카운트 값을 증가시킵니다(이제 카운트 = 2).

숫자(12)를 10으로 나누면 12가 1이 됩니다.

이제 while 루프는 0보다 1이 큰지 확인합니다. 1은 0보다 크기 때문에 다시 while 루프에 들어가 카운트 값을 증가시킵니다(이제 카운트 = 3).

숫자(1)를 10으로 나누면 1이 0이 됩니다.

이제 while 루프는 참이 아니기 때문에 0보다 큰 0인지 확인하려고 합니다. while 루프는 실행되지 않습니다.

while 루프 후에 count(count =3)를 반환할 return 문이 있습니다.

Time Complexity : O(n) 
Auxiliary Space : O(1) 

이제 재귀 방법을 사용할 시간입니다.

  public int countByRecursion(int number) {
    if (number == 0) {
      return 0;
    }
    return 1 + countByRecursion(number / 10);
  }

기본 조건은 숫자가 0인지 여부를 확인합니다.
0이면 0을 반환하고 재귀 호출을 중지합니다.

그렇지 않은 경우 숫자를 10으로 나누고 해당 호출 결과에 1을 추가하여 재귀 호출을 수행합니다.

Time Complexity : O(log(n)) 
Auxiliary Space : O(log(n))

이제 로그 방법

public int countByLog(int number) {
    return (int) Math.floor(Math.log10(number) + 1);
  }

간단해보이네요!!! 이는 또한 countByRecursion 및 countByIteration과 비교할 때 효율적인 방법입니다.

이것의 이면에 있는 아이디어는 우리가 log10(123)을 할 때 우리가 바닥을 취하면 2.089905111439398 우리가 2.0을 얻은 다음 그것에 1을 더하여 3.0이 되도록 하는 것입니다. 결국 우리는 그것을 int로 캐스팅하여 3이 됩니다.

Time Complexity : O(1)
Auxiliary Space : O(1)

If you are at interview you can use the Log method.

이것은 내 DSA 준비 시리즈의 일부입니다.
Day 1 to 9 : 알고리즘 분석
10일: