[프로그래머스] 점프와 순간 이동 - JAVA

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

풀이

아무리 생각해도 bfs와 dp 만 생각이 났다.

그런데 n이 최대 10억까지 될수 있으므로 bfs와 dp로 풀 경우에는 시간초과가 발생한다.

그래서 1부터 10까지 표를 그려 세어보니 특징이 나타났는데 바로 이진수의 1의 개수라는 것이었다. 

따라서 bitCount 함수를 이용하여 문제를 풀었다.

하지만 정석적으로(?) 푸는 방법도 있어 그 코드도 한번 첨부해보겠다

 

코드

bitCount를 이용하여 풀 경우

public class Solution {
    public int solution(int n) {
        
        int answer = Integer.bitCount(n);
    
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        // System.out.println(bitcnt);

        return answer;
    }
    
}

정석처럼 풀경우

public class Solution {
    public int solution(int n) {
        
        int ans = 0;
        
        while(n > 0){
            if(n%2 == 0){
                n = n/2;
            }
            else{
                n -= 1;
                ans +=1;
            }
        }
        
        
        
        return ans;
        
    }
    
   
}