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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

코드

    public int solution(int n) {
        return Integer.bitCount(n);
    }

제출 결과

후기

한 줄의 코드지만, 저렇게 가능한지 유추하기 위해 고민하는 시간은 짧지 않았다..

 

일단 텔레포트의 특성을 생각해보면, 이전까지의 이동거리*2를 텔레포트할 수 있다.

 

그렇다는 것은 주어진 거리N을 계속 2로 나누면 계속 텔레포트만 해서 이동할 수 있게 된다.

 

예를 들어 N=6이라고 하면

 

6/2 = 3 

3/2 = 1

 

이 된다. 6만큼의 거리를 이동하기 위해서 거리 3에서 텔레포트를 했고, 3만큼의 거리를 이동하기 위해서 거리 1에서 텔레포트를 했다.

 

그리고 거리 1은 최소 이동거리이기 때문에 1 이하의 거리는 계산해줄 필요가 없다.

 

그런데 여기서 최초 거리 6의 이전 이동거리 3을 구했을 때는 나머지가 0이기 때문에 점프를 할 필요가 없었다.

 

그러나 3의 이동거리인 1을 구할 때는 나머지가 1이 생겼다. 그렇다는 것은 1만큼 점프를 더해주어야 한다.

 

즉, 3까지 이동하기 위해서는 거리 1에서 텔레포트! 해서 2로 이동한 후 + 1을 해주어야 한다.

 

위의 예시로 유추해보면 주어진 거리 N을 2로 나눌 때, 나머지가 0인 경우 1인 경우 2가지로 나뉘게 된다.

 

0인 경우는 신경을 안 써도 되지만 1인 경우는 반드시 1만큼 점프를 해주어야 한다. ( 텔레포트를 하기 위해서! )

 

이렇게 마지막 예시인 5000을 2로 나누어가며 나머지를 찾던 도중.. 아 이건 주어진 N을 2진수로 바꾸면 나머지가 1인 경우는 1로 표시되겠구나..라는 것을 캐치할 수 있었다.

 

그리고 Integer클래스에서 주어진 정수 n의 2진수 값에 해당하는 1의 개수를 반환해주는 Integer.bitcCount()를 활용하였다.

 

내가 풀은 알고리즘 문제 중에 가장 적은 코딩을 한 문제였던 것 같다..

 

이번 문제는 되게 뿌듯했다..ㅎ