Binary Prefix Divisible By 5

1018. Binary Prefix Divisible By 5 Acceptance 43.6%

NOTE

블로그라기 보다는 생각나는 생각나는 대로 두서없이 적는 낙서장이라고 보면 될것 같다.

2019년 4월 3일 15:42~16:00

문제

1. 0,1로 이뤄진 배열(A)이 주어진다.
2. 이때, 배열 A를 [0..A.length-1]까지 순회하면서 0부터 i까지의 이진수를 10진수로 변환했을때 5로 나눠떨어지면 해당 인덱스의 값은 true, 아니면 false를 리턴한다.
3. 1 <= A.length <= 30000

생각 흐름 - 무식하게 풀기

1. A의 길이가 가장 간단한 것은 StringBuilder로 계속 append하면서 Integer.parseInt()로 바꿔서 5로 나눈 나머지가 0이면 true 아니면 false로 하는 것인데, 31자리를 넘어가는 순간부터 에러가 날 것이다.
2. 그럼 규칙성을 발견해야한다.
3. 1의 자리를 2배한 다음 1 혹은 0을 더하고 다음에 5로 나머지 연산하면 끝?
4. 검증해보자.

   [1,1,1,1,1,1,1]
   1 - 1
   3 - 3
   7 - 7
   15 - 5
   31 - 1
   63 - 3
   127 - 7