[백준 알고리즘] Q1094 막대기 - Integer.bitCount(num)

1. Java 구현

            
package Q1094;


import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        System.out.println(getResultByStack(n));
        System.out.println(geResultByBitCount(n));

        bw.close();
    }

    public static int geResultByBitCount(int num) {
        return Integer.bitCount(num);
    }

    public static int getResultByStack(int num) {
        int size = 64;
        Stack stack = new Stack<>();
        stack.add(size);
        int sum = 0;
        while((size + sum) != num) {
            size = stack.pop() / 2;
            if(size + sum < num) {
                stack.add(size);
                sum += size;
            }
            stack.add(size);
        }
        return stack.size();
    }

}

2. 코드설명

 막대기를 절반으로 계속 잘라서 원하는 갈이의 막대기를 구하는 문제이다. 처음 막대기의 길이는 64이다.

 예들들어 23 길이의 막대를 얻기 위한 과정을 보자

  1.  막대기의 길이는 64 이므로, 23보다 크다.

  2. 막대기를 절반으로 자르고, 나머지 절반은 버린다.

  3. 막대기의 길이가 32가 되었고, 여전히 23보다 크다. 다시 32를 반으로 나눈다.

     반으로 나눈 16은 23보다 작기 때문에 16은 따로 보관한다.

  4. 나머지 16을 반으로 쪼갠다. 보관한 16과 쪼갠 8을 더했을 때, 여전히 23보다 크기 때문에 나머지 8을 버린다.

  5. 다시 8을 쪼갠다. 쪼갠 4와 보관하고 있는 16을 더했을 때, 23보다 작기 때문에 4도 보관한다. (현재 : 16 4 보관)

  6. 다시 4를 쪼갠다. 쪼갠 2와 보관하고 있는 막대기들을 더했을 때, 23보다 작기 때문에 2도 보관한다. (현재 : 16 4 2 보관)

  7. 다시 2를 쪼갠다. 쪼갠 1과 보관하고 있는 막대기들을 더했을 때, 23이 된다. 1도 보관한다. (현재 : 16 4 2 1 보관)

  8. 보관하고 있는 막대기의 갯수를 출력한다. 

이 문제를 두가지 방식으로 해결할 수 있다. 첫번째는 위의 과정을 그대로 코드를 옮기는 것이다. 바로 스택을 사용해서!

 (1) 스택 사용

  스택은 LIFO 이기 때문에 마지막에 삽입한 데이터를 제일 먼저 꺼낼 수 있다. 방금 직전에 쪼갠 막대기를 이용해서 계속 계산을 해야 하기 때문에 큐가 아닌 스택을 사용했다.

  그리고, 계속해서 삽입과 삭제를 반복해야 하기 때문에 List 보다는 Stack 효율적이라고 판단했다. 

 스택도 나름 나쁘지 않는 방법이라고 생각했는데, 다른 개발자분들이 작성하는 코드 보면서 더 심플한 코드를 보았다.

  (2) Integer 클래스에서 제공하는 정적 메소드 bitCount(n) 메소드 활용

   이 문제를 잘 보면 막대기를 반으로 계속해서 나눈다. 막대기들은 16, 8, 4, 2, 1 과 같은 형태로만 나눌 수 있다. 이 수를 다른게 표현하면 2^4, 2^3, 2^2, 2^1 ,2^0 이다.

   모두 2의 거듭재곱을 나타낼 수 있다. 결국은 2진법으로 표현할 수 있다는 이야기이다. 결국은 막대기의 길이를 이진법으로 변경하고, 이진법에서 1의 갯수를 구하면 된다.

   그리고 bitCount 메소드가 2진법에서의 1의 갯수를 구할 수 있는 정적메소드이다. 이 메소드를 사용하면 한줄에만 구할 수 있다.

3. Pain Point

 문제를 푸는 것은 어렵지 않았지만, 이 문제가 2진법으로 생각해서 풀면 쉽게 풀 수 있을거라고는 생각을 못했다. 

 요즘에 문제를 어떻게 풀면 효율적이라고 생각하기보다는, 문제 해결에만 너무 급급해진거 같다.