[랜덤 마라톤] 저울 추 만들기(2205)

1. 문제 풀이 아이디어

• 납덩어리를 n부터 역순으로 선택하고, 주석덩어리를 더해 2의 거듭제곱이 되는 최대값을 구하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int n = Integer.parseInt(bufferedReader.readLine());
        int result[] = new int[n + 1];
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        for (int i = n; i >= 1; i--) {
            int sum = i + list.get(list.size() - 1);
            String bin = Integer.toBinaryString(sum);
            int len = bin.length();
            if (!bin.substring(1).contains("1")) {
                result[i] = list.remove(list.size() - 1);
                continue;
            }
            int pow = (int) Math.pow(2, len - 1);
            result[i] = list.remove(list.indexOf(pow - i));
        }
        for (int i = 1; i <= n; i++) {
            stringBuilder.append(result[i]).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• list에 1부터 n까지 차례대로 저장한다.

• n부터 시작해 list의 최대값과 더한 값을 2진수로 변환하여 bin에 저장한다.

• bin의 두 번째 자리부터 1이 없으면, 해당 값은 2의 거듭제곱이므로, result[i]에 list의 최대값을 저장하고 list에서 삭제한다.

• 반대로 bin에 1이 있으면, bin의 길이에서 1을 뺀 값으로 최대 거듭제곱수를 구한 뒤, 그 값에서 i를 뺀 값을 result[i]에 저장하고 list에서 그 값을 삭제한다.

• 이 과정을 n에서 1까지 반복하면 문제의 답을 구할 수 있다.

4. 더 좋은 코드 리뷰

public class Main {
    static int[] two;
    static StringBuilder sb = new StringBuilder();

    static int solve(int n, int[] ans) {
        int s = 0, e = 14, mid;
        while (s + 1 < e) {
            mid = (s + e) >> 1;
            if ((1 << mid) <= n)
                s = mid;
            else
                e = mid;
        }
        int val = 1 << s;
        for (int i = n - (n - val) * 2; i <= n; i++)
            ans[i] = Math.abs(i - val * 2);
        return n - (n - val) * 2 - 1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()), nn = n;
        int[] ans = new int[n + 1];
        while ((nn = solve(nn, ans)) != 0);
        for (int i = 1; i <= n; i++)
            sb.append(ans[i]).append('\n');
        System.out.print(sb);
    }
}

• 이진 탐색을 사용해 n보다 작거나 같은 2의 제곱 수 중에서 가장 큰 값을 구하고, 그 값을 val에 저장한다.

• n - (n - val) * 2부터 n까지 반복하면서 Math.abs(i - val * 2) 연산을 수행하여 다른 덩어리의 값을 ans 배열에 저장한다.

• 이 과정을 n이 0이 될 때까지 반복하여 문제를 해결한다.