새로 배운 것: 2진법 변환은 생각보다 까다롭다 (숫자 메모리 저장 방식)
처음에는 1~n까지 숫자 만들어서 각 요소마다 2진법으로 바꾸고 조인 시키면 안되나 라고 생각했는데 안된다.
값이 작으면 답대로 나오는데 한 n = 20부터 값이 이상하게 나오고 n 엣지포인트 찍으면 NaN 뜸)
JavaScript data types and data structures - JavaScript | MDN (mozilla.org) 문서를 보면
Number
According to the ECMAScript standard, there is only one number type: the double-precision 64-bit binary format IEEE 754 value
64비트까지 수 표현이 가능하다고 한다.
메모리 저장 방식을 생각하면 당연함 (비트가 총 64자리밖에 못 들어감)
솔루션
시간 복잡도: O(N)
알아야 할 개념
- Bit shift << >> 연산자
https://www.interviewcake.com/concept/java/bit-shift
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Left_shift
- 2진법 ↔ 10진법 완벽하게 안된다. (메모리 제한이 있다)
새롭게 알게 된 것
1. 수형 표현 지수 표기에서 1e21부터 걍 문자열 그대로 퉁침
https://velog.io/@ordo_92/수형-표현-Math-expression-JS 참고
→ 아래 코드에서 b, b1 값 보면 알 수 있음
2. parseInt 메서드는 진수변환에 적합한 메서드가 아님
parseInt는 문자열 표현을 가지고 수를 만드는 메서드임
문서 가서 보면
The parseInt() function parses a string argument and returns an integer of the specified radix (the base in mathematical numeral systems). 라고 적혀있음
parseInt(문자열로 이루어진 숫자, 나타낼 진법) 이렇게 문자열로 나타내진 걸 바꾸는 거지
1e21을 2진법으로 바꾸는 거에 의미가 있지는 않음.
진법간 변환은 똑같은 수인데 문자열 표현을 바꾸거나, 별로 안 쓰지만 문자열 표현이 같은데 진법이 달라서 수가 달라지는 경우인데
지금 a, b 이런 애들을 수로 선언했기 때문에 달라질 수 있는 건 문자열 표현밖에 없고, 그건 parseInt로 하는 게 아님
따라서 shift 써서 풀이해야함
3. 자스는 Number, BigInt로 숫자 저장하고 Number같은 경우에는 C언어 double이랑 같은 방식으로 저장됨 (부동소수점 주의해야함)
이때 BigInt는 수 제한이 없는데 (메모리 저장 방식이 특이함) 관련해서 더 찾아보다가 그만둠
BigInt 로 이 문제 풀이 할 수 있는지 궁금함
시간 낭비가 좀 많아서 일단 패스
4. 자스 안전한 숫자 → 2^53 - 1 까지 표현 가능
Number.MAX_SAFE_INTEGER - JavaScript | MDN (mozilla.org)
자스 Number 는 메모리에 IEEE - 754 형식을 이용해서 저장한다.이 형식에 의해 (signed) 2^53 - 1 값 까지는 정확히 IEEE - 754 로 표현될 수 있지만, 범위를 넘어선 숫자는 IEEE - 754 로 직접 표현될 수 없으며 가까운 수나 0 으로 반올림 한다.