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

서론

오늘은 오랜만에 알고리즘을 풀었다. 이번에 풀 알고리즘 문제는 무엇이냐!! 하면은? 뭘까요~~~?

포켓몬 박사님: 뭘까요~~~?

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

코딩테스트 연습 - 점프와 순간 이동

바로 이 문제이다. 생각해보니 이미 제목으로 스포를 해놓았으니 저렇게 숨겨도 당연히 알겠구나... 흠흠...

본론

일단 이 문제는 처음에는 어떤 알고리즘이 있을까 하면서 봤었는데 계속 봐도 문제의 규칙을 모르겠었다. 그러다가 처음으로는 다음의 방법을 생각했었다.

 

N이 홀수면 짝수로 만들어서(+1) 2로 나누고 나눈 값이 홀수면 체크하자.
만약, N이 1이 되면 한번 더 체크하고 반복을 종료한다.
체크한 값의 총 합에 1을 더한 값이 답이다!!

 

이렇게 풀어봤는데, 당연히 안됐다. 분명히 짝수가 계속 나오므로 (2*x 만큼 증가하는 형태를 보이므로) 짝수를 이용하는 것 같은데... 하고 너무 답답해서 문제 풀이의 어떤 분이 올리신 힌트를 보았다.

 

 

바로 이 간단하디 간단한 힌트였다.

 

이 힌트를 보고 나누기를 생각해봤다. 그래서 테스트 케이스의 값들을 나눠보니 나머지 1의 개수 (몫이 1일 때 포함) 이었다!! 그래서 이를 이용해서 풀어보니 문제의 정답률이 40%정도 였다.

 

 

왜냐면 나는 계속 홀수면 짝수로 만들어주고 있었기 때문이다!!(불필요한 연산)

그래서 그 부분을 빼고 다시 아래와 같은 풀이로 진행했더니 문제 풀이에 성공했다!

 

N이 0보다 크면 반복
N이 홀수면 카운트 1 증가
N = N/2

이 얼마나 쉬운 답이었나...ㅠㅠ

아래는 정답 소스코드이다.

 

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

 

결론

정답을 알고 문제를 다시보니... 문제 설명자체가 나눗셈 그자체였다. 

 

다음은 N=5일 때의 문제풀이 설명이다.

 

• 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

 

이를 거꾸로 봐보자...

1. 1 칸을 앞으로 점프하면 도착
2. 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동

3. 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동

4. 처음 위치 0 에서 1 칸을 앞으로 점프

 

위의 순서와 아래 그림에 적혀있는 순서대로 매칭이 된다!

5를 나눴을 때 모습(나머지는 생략)

6의 경우나, 5000의 경우도 모두 동일하다. 왼쪽의 2는 순간이동을 의미하고 홀수인 몫은 (결국에 나누면 나머지 1이 생기므로) 점프 1을 의미한다.

 

다음에는 5분안에 풀어주겠어..^^