일단 하나를 해보자

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 상수값을 나누고 그 나머지로 사용한다는

문제의 조건이었음!!

875. Koko Eating Bananas

수업 때 들은 내용 복습 겸 다시 풀었다. 

--

코코는 바나나 먹는 걸 좋아해요. n개의 바나나 더미가 있고, i번째 더미에는 [i]개의 바나나가 있습니다. 경비원은 떠났고 몇 시간 후에 다시 올 것입니다.

코코는 시간당 바나나 섭취 속도 k를 결정할 수 있습니다. 매 시간마다 그녀는 바나나 더미를 선택하고 그 더미에서 k개의 바나나를 먹습니다. 더미에 k개 미만의 바나나가 있으면 대신에 바나나를 모두 먹고 이 시간 동안 더 이상 바나나를 먹지 않습니다.

코코는 천천히 먹는 것을 좋아하지만 경비원이 돌아오기 전에 바나나를 모두 먹고 싶어합니다.

그녀가 h 시간 내에 모든 바나나를 먹을 수 있도록 최소 정수 k를 반환합니다.

--

수업때 받은 코드로 풀이

원숭이가 주인이 오기 전 h 시간동안 바나나를 먹으려고 한다. 

pile 바나나 더미  = [ 30, 11, 23, 4, 20] 

h = 5

원숭이가 5시간 내에 먹을 수 있는 최소 바나나 갯수 k 를 구해야한다. 

예를 들어 원숭이가 1시간에 20송이를 먹을 수 있다고 치자

30송이는 20송이 + 10송이이다. 그러면 이 원숭이는 "그녀는 바나나 더미를 선택하고 그 더미에서 k개의 바나나를 먹습니다. 더미에 k개 미만의 바나나가 있으면 대신에 바나나를 모두 먹고 이 시간 동안 더 이상 바나나를 먹지 않습니다."

이 조건에 의해 30송이를 먹는데 2시간이 걸리는 셈이다. 

그러면 1시간에 20송이를 먹는 원숭이는 

2시간 + 1시간 + 2시간 + 1시간 + 1시간 = 총 7시간이 걸린다. 5시간 내에 먹기 실패~!

이걸 바이너리 서치를 이용해 풀어보자

우리가 구해야할 k의 범위를 정하고 

중간값 m을 지정해 그 m으로 piles 안에 있는 바나나를 먹었을 때 h보다 크면 실패!

h보다 작거나 같으면 시간 안에 먹기 성공!!

left 1, right0 을 준 건 초기화를 위함

isEdible이 true면 그 중간값이 답이다

right로 리턴하는 까닭은  m 변수 선언이 로컬로 되어있어서. 

중간값을 구할 때 나는 보통 (left + right ) /2 로 구하는데 이번에 다른 방법을 알았다.

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left =1 , right =0;
     
        for (int p: piles){
            right = Math.max(right, p);
      
        }
        while(left < right){
             
            int m = left +(right -left)/2;
           
            if ( isEdible(m, piles,h)){
                right = m;
         
            } else{
                left = m + 1;
            
            }
        }
     
        return right;
    }
    private boolean isEdible(int unit, int[] piles, int h){
    
        int curHour = 0;
        for (int p: piles){
          
            curHour += p /unit + (p%unit > 0 ? 1:0);
          
            if (curHour > h){

                return false;
            }
        }
        return true;
    }
}

int m = left + (right - left) /2;

로 하는 이유는 오버플로우를 방지하기 위해!

만약 left와 right가 각각 int의 최대범위값을 가지고 있다면 기존 코드대로 하면 나누기 2를 하기 전에 오버플로우 현상이 발생한다.