프로그래머스(12911) 다음 큰 숫자[bitCount], 프로그래머스(12945) 피보나치 수[피보나치 수열]

프로그래머스(12911) 다음 큰 숫자[bitCount] 

 

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항

• n은 1,000,000 이하의 자연수 입니다.

---

 

입출력 예nresult

78	83
15	23

입출력 예 설명

입출력 예#1
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.

풀이

Integer.bitCount는 숫자를 2진수로 하였을때 1의 개수를 파악하여 int(정수)값으로 반환한다.

ex ) 78 = 1001110  > 4를 반환

class Solution {
    public int solution(int n) {
        int nextBigNumber = n + 1; // 받아온 매개변수에 1을 더하여 저장
        int nBitCount = Integer.bitCount(n); // n을 2진수로했을때 1의 갯수를 파악한다
        
        while(Integer.bitCount(nextBigNumber) != nBitCount){
        	 // n의 1의 개수와 nextBigNumber의 1의 개수가 같아질때까지 반복
             
            nextBigNumber++;
        }
        return nextBigNumber;
        // n의 1의 개수와 nextNigNumber의 1의 개수가 같은 번호를 반환
        
    }
}

 

프로그래머스(12945) 피보나치 수[피보나치  수열]

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

입출력 예nreturn

3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

풀이

피보나치 수열이란 수학에서 유명한 수열 중 하나이다

피보나치 수열은 다음과 같은 재귀적 방식으로 정의 된다.

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n >= 2)

0과 1일땐 값이 위와 같고 2보다 같거나 큰 숫자는 F(n) = F(n-1) + F(n-2) (n >= 2) 와 같은 공식을 가지게 된다

예를 들어 n이 5이면은 F(5) = F(4) + F(3) > F(5) = 2 + 1 F(5)의 값은 3이된다 

                                    // F(4) = 2 /  F(3) = 1 

피보나치 수열을 참고하자 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... 

F(0)	0
F(1)	1
F(2)	1
F(3)	2
F(4)	3
F(5)	5
F(n)	F(n-1) + F(n-2)

class Solution {
    public int solution(int n) {
        int[] fibonacci = new int[n + 1]; 
        // 피보나치 수열은 F(4)가있어야 F(5)를 구할수있다 그럼으로 F(5)째의 값을 알고싶다면
        // 배열이 6개 필요하다
        
        fibonacci[0] = 0; // F(0) = 0
        fibonacci[1] = 1; // F(1) = 1
        // 두개의 값이 있어야 밑으 for문에서 연산이 가능하다
        
        for(int i = 2; i <=n; i++){ // n의 크기만큼 반복 실행
            fibonacci[i] = (fibonacci[i - 1] + fibonacci[i-2]) % 1234567;
            // 배열에 피보나치 값을 계산하는 식 
            // i가 2라고 가정하면 fibonacci[1] + fibonacci[0]
            // 						1         +     0   % 123456  = 1 이된다
            // %1234567을 사용하는 이유는 큰 수 처리를 피하기 위함 효율적인 연산을 위해
            // n이 100이라 하면 값은 354,224,848,179,261,915,075로 나온다 이 값을
            // 1234567로 나머지를 구하면 1085682 로 줄여져 처리하는 메모리와 시간 측면에서 효율이 상승한다
        }
        return fibonacci[n];
    }
}