1680. Concatenation Of Consecutive BinaryNumbers

https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/description/

 

주어진 n의 값을 연속적으로 이진법으로 만들고 

그 값을 다시 10진법으로 만들어 구하는 문제

 

 

최종 코드 

n이 12일때

package 리트코드;

public class ConcatenationOfConsecutiveBinaryNumbers1680 {
    private static final int MOD = 1000000007;

    public int concatenatedBinary(int n) {
        //long은 19자리수 가능
        long result = 0;

        for (int i = 1; i <= n; i++) {
            int num = i;
            StringBuilder binaryStr = new StringBuilder();
            while (num > 0) {
                binaryStr.append(num % 2); //나머지 넣기
                num /= 2; //2나누기

            }

            binaryStr.reverse();
            String binary = binaryStr.toString();

            //비트 연산을 통해 이진 문자열을 추가
            for (char c : binary.toCharArray()) {
                //2로 곱하고 나머지를 더하는 식임
                // '0'을 빼면 수로 변환됨
                //MOD로 나눈 나머지로 구하는 이유는 매우큰 숫자 다룰 때 오버플로우 방지하고 결과를 적절한 범위내에서 유지하기 위함임
                result = (result * 2 + (c - '0')) % MOD;
                System.out.println("result = " + result);

            }


        }
        return (int) result;

    }

    public static void main(String[] args) {
        int n = 12;
        ConcatenationOfConsecutiveBinaryNumbers1680 concatenationOfConsecutiveBinaryNumbers1680 = new ConcatenationOfConsecutiveBinaryNumbers1680();
        int result = concatenationOfConsecutiveBinaryNumbers1680.concatenatedBinary(n);
        System.out.println("result = " + result);

    }
}

 

result = 1
result = 3
result = 6
result = 13
result = 27
result = 55
result = 110
result = 220
result = 441
result = 882
result = 1765
result = 3531
result = 7063
result = 14126
result = 28253
result = 56507
result = 113015
result = 226031
result = 452062
result = 904124
result = 1808248
result = 3616497
result = 7232994
result = 14465988
result = 28931977
result = 57863955
result = 115727910
result = 231455821
result = 462911642
result = 925823285  -> 여기까진 값네 925823285 
result = 851646563  (-> 나누지 않은 값이 1851646570 = 925823285 *2  로, 10자리여서 MOD로 나눠지게 됨. 그 나머지값임)
result = 703293120
result = 406586234
result = 813172469
result = 626344932
result = 252689857
result = 505379714
result = 505379714

 

근데 만약 MOD를 나눈 나머지 값으로 구하지 않는다면?
 private static final int MOD = 1000000007;

result = (result * 2 + (c - '0'));

 

 

result = 1
result = 3
result = 6
result = 13
result = 27
result = 55
result = 110
result = 220
result = 441
result = 882
result = 1765
result = 3531
result = 7063
result = 14126
result = 28253
result = 56507
result = 113015
result = 226031
result = 452062
result = 904124
result = 1808248
result = 3616497
result = 7232994
result = 14465988
result = 28931977
result = 57863955
result = 115727910
result = 231455821
result = 462911642
result = 925823285  -> 9자리 

--여기까지 같음-- 
result = 1851646570 = 925823285 *2  

result = 3703293141  =  1851646570 * 2 +(나머지 1 더함 )

result = 7406586283
result = 14813172567
result = 29626345135
result = 59252690270
result = 118505380540 
result = -1753703748 = 118505380540 * 2 = 237,010,761,080

 

근데 long이 19자리수까지 가능한데도 굳이 MOD를 나누는 이유는 

수의 크기가 너무 커져서 오버플로우가 일어나는 것을 방지하기 위함.

MOD 상수값을 나누고 그 나머지로 사용한다는

 

문제의 조건이었음!!