[프로그래머스/LV2] Summer/Winter Coding(~2018) - 점프와 순간 이동 - greedy, bit (Java)

Summer/Winter Coding(~2018) - 점프와 순간 이동

🙋‍♂️ 들어가며

아이언슈트를 활용해 건전지 사용량의 최솟값을 구하는 문제이다.

목표

• 한번에 k칸 점프 -> 건전지 사용량 += k
• 텔레포트 (현재까지 온 거리 * 2) -> 건전지 x

0부터 x까지 구해보았다

# tc-1 : N = 5
0 -> 1(++) -> 2(1*2) -> 4(2*2) -> 5(++)

# tc-2 : N = 6
0 -> 1(++) -> 2 (1*2) -> 3(++) -> 6(3*2)

# tc-3 : N = 5000

N : 5000 을 구하려니 너무 복잡하더라

그래서 다시 바꿔생각해서 N -> 0으로 거꾸로 계산해보았다

5000 -> 2500 -> 1250 -> 625(홀) -> 312 -> 156 -> 78 -> 39(홀) -> 19(홀) -> 9(홀) -> 4 -> 2 -> 1(홀) -> 0

5가 나오네?

다른 testcase로

N = 9를 보았다

0 -> 1(++) -> 2(12) -> 4(22) -> 8(4*2) -> 9(++)

9(홀) -> 4 -> 2 -> 1(홀) -> 0

이어서 N = 19

0 -> 1(++) -> 2(12) -> 4(22) -> 8(42) -> 9(++) -> 18(92) -> 19(++)

19(홀) -> 9(홀) -> 4 -> 2 -> 1(홀) -> 0

즉 N -> 0 방향으로 홀,짝 조건을 이용해 그리디 코드가 맞다고 판단이 들어서 다음과 같이 코드를 작성했다

✅ 정답 코드 (greedy)

public class Solution {
    public int solution(int n) {
        int cnt = 0;
        
        // 1. 거꾸로 n -> 0
        while (n > 0) {
            
            // 1-1. 홀
            if (n % 2 == 1) {
                n /= 2;
                cnt++;
            }
            
            // 1-2. 짝
            else if (n % 2 == 0) {
                n /= 2;
            }
        }

        return cnt;
    }
}

그리고 생각해보니 2배라서 2진 비트로도 풀이가 가능할 지 시도해보게 되었다

| 대상 | 16384 | 8192 | 4096 | 2048 | 1024 | 512 | 256 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | |—:|—:|—:|—:|—:|—:|—:|—:|—:|—:|—:|—:|—:|—:|—:|—:| | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | | 315 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | | 5000 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |

315(홀) -> 157(홀) -> 78 -> 39(홀) -> 19(홀) -> 9(홀) -> 4 -> 2 -> 1(홀) -> 0

답 : 5

어????? 2진 비트 풀이도 맞겠다는 생각이 들었다

그래서 다음과 같이 구현했으나 String temp = "" temp += ch 일 경우 매번 새로운 String을 만든다고 해서 시간초과가 나게 되었다

❌ 오답 코드 (2진 bit)

public class Solution {
    public int solution(int n) {
        int cnt = 0;
        
        // 1. 비트변환기
        String bit = bit_converter(n);
        
        // int x = 315;
        // String test = bit_converter(x);
        // System.out.println(bit);
        // System.out.println("--------");
        // System.out.println(test);
        
        
        // 2. 결과
        for (int i = 0; i < bit.length(); i++) {
            char ch = bit.charAt(i);
            if (ch == '1') cnt++;
        }
        
        return cnt;
    }
    
    
    // 2. 함수 : 2진 비트 변환기
    static String bit_converter(int n) {
        String temp = "";
        
        while (n > 0) {
            // 2-1. 짝수면?
            if (n % 2 == 0) {
                temp += '0';
                n /= 2;
            }
            // 2-2. 홀수면?
            else if (n % 2 == 1) {
                temp += '1';
                n /= 2;
            }
        }
        
        String res = "";
        for (int i = 0; i < temp.length(); i++) {
            char ch = temp.charAt(temp.length()-1-i);
            res += ch;
        }
        
        return res;
    }
    
    
}

StringBuilder를 사용하면 내부 Buffer에 계속 추가하는거라 훨씬 효율적이기에 StringBuilder로 교체하게 되었다

✅ 정답 코드 (2진 비트)

public class Solution {
    public int solution(int n) {
        int cnt = 0;
        
        // 1. 비트변환기
        String bit = bit_converter(n);
        
        int x = 315;
        String test = bit_converter(x);
        // System.out.println(bit);
        // System.out.println("--------");
        // System.out.println(test);
        
        
        // 2. 결과
        for (int i = 0; i < bit.length(); i++) {
            char ch = bit.charAt(i);
            if (ch == '1') cnt++;
        }
        
        return cnt;
    }
    
    
    // 2. 함수 : 2진 비트 변환기
    static String bit_converter(int n) {
        StringBuilder sb = new StringBuilder();
        String res = "";
        
        while (n > 0) {
            // 2-1. 짝수면?
            if (n % 2 == 0) {
                sb.append('0');
                n /= 2;
            }
            // 2-2. 홀수면?
            else if (n % 2 == 1) {
                sb.append('1');
                n /= 2;
            }
        }

        res = sb.reverse().toString();
        return res;
    }
    
    
}