find number 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

• 홀수 숫자는 규칙이 있음1 3 5 7 9

  11	13	15	17	19
  31	33	35	37	39
  51	53	55	57	59
  71	73	75	77	79
  91	93	95	97	99
  101	103	105	107	109

• 위 규칙에 따라서 5번을 기점으로 반복되는 것을 알수 있습니다.
• 그러므로 5로 나눈 나머지수가 자리수라는것을 알수 있습니다.
• 각각의 자리수를 안다면 그 자리수이용해서 어떤숫자가 올지 알수 있음(1,3,5,7,9)
• 13번째 홀수 숫자를 예로 든다면
  • 13에서 가장 오른쪽(1의 자리)에 있는 숫자는 3번째 입니다.
  • 홀수 규칙에 따라서 세번째 오는 수는 5입니다.
  • 13에서 두번째로 오른쪽에 있는 숫자(10의 자리)는 2번째 입니다.
  • 홀수 규칙에 따라서 두번째 오는 수는 3입니다.
  • 결론적으로 13번쨰 홀수 숫자는 35입니다.
• 27번째 홀수 숫자를 예로 든다면
  • 27에서 가장 오른쪽(1의 자리)에 있는 숫자는 (27%5) 2번째 입니다.
  • 홀수 규칙에 따라서 두번째 오는 수는 3입니다.
  • 위에서 계산한 자리수를 제외하면 27-27%5 = 27/5=5 입니다.
  • 두번째로 오른쪽에 있는 숫자(10의 자리)는 (5%5) 5번째 입니다.
  • 홀수 규칙에 따라서 다섯번째 오는 수는 9입니다.
  • 결론적으로 27번쨰 홀수 숫자는 93입니다.
• 위의 규칙에는 조금 맞지 않는것이 있습니다. 예를 들어 5%5는 0입니다. 하지만 우리가 원하는것은 위의 규칙대로 5가 나오기를 바랍니다.

- n % 5 = 0 //5th number = 9
- n % 5 = 1 //1th number = 1
- n % 5 = 2 //2th number = 3
- n % 5 = 3 //3th number = 5
- n % 5 = 4 //4th number = 7

• 이를 위해서 n-1를 해줍니다

- n-1 % 5 = 0 //1th number = 1
- n-1 % 5 = 1 //2th number = 3
- n-1 % 5 = 2 //3th number = 5
- n-1 % 5 = 3 //4th number = 7
- n-1 % 5 = 4 //5th number = 9

• 마지막으로 0,1,2,3,4가 나왔을때 우리가 실제 원하는 숫자는 1,3,5,7,9 입니다. 이를 최적화 하기위해서 2을 곱하고 1을 더해줍니다.

0*2+1=1
2*2+1=3
3*2+1=5
4*2+1=7
5*2+1=9

시간복잡도: O(log n), 공간복잡도: O(1)

https://github.com/eunhanlee/findNumber_Solution_gfg.git

class Solution
{
    public long findNumber(long N)
    {
        // 최종 결과를 저장할 변수
        long result = 0;
        // 자릿수를 나타내는 변수 (1, 10, 100, ...)
        long position = 1;

        while (N > 0)
        {
            // N에서 1을 빼고 5로 나눈 후, 홀수 자릿수를 구함
            long oddDigit = ((N - 1) % 5) * 2 + 1;
            // N에서 1을 빼고 5로 나눔 (다음 자릿수를 계산하기 위해)
            N = (N - 1) / 5;
            // 현재 자릿수에 홀수 자릿수를 곱한 값을 결과에 더함
            result += oddDigit * position;
            // 다음 자릿수로 이동
            position *= 10;
        }

        // N번째 홀수 숫자를 반환
        return result;
    }
}

설명

• 주어진 정수 N은 연산 과정에서 반복적으로 5로 나누어져 줄어듭니다. 이 과정에서 홀수 자릿수 숫자들을 생성합니다. 반복문은 N이 0보다 클 동안 계속 진행됩니다.
• 한 번의 반복이 일어날 때마다 N은 (N - 1) / 5로 업데이트됩니다. 이 과정은 N이 절반 이상 감소하므로 매 반복마다 N이 크게 줄어듭니다. 반복이 일어날 때마다 N이 거의 절반으로 줄어들기 때문에 O(log N)이라고 할 수 있습니다.