ソートを利用したアルゴリズム問題解決

アルゴリズムの主要なプロセス

1. 2進数の1の個数を数える:

   • 与えられた配列 nums の各整数について、その数を2進数に変換したときの1の個数を数えます。
   • cur 変数を用いて各整数を2進数に変換し、ループを通して1の個数（cnt）をカウントします。

2. 優先度キューに追加:

   • 各整数（num）とその数の1の個数（cnt）を Node オブジェクトとして作成し、優先度キュー pq に追加します。
   • PriorityQueue<Node> は Node オブジェクトの compareTo メソッドを使用してソートされます。compareTo メソッドは次の基準に従ってノードをソートします：
     • 1の個数（cnt）が少ない順に昇順でソート。
     • 1の個数が同じ場合は、整数の値（val）が小さい順にソート。

3. ソート結果を配列として返す:

   • 優先度キューからノードを一つずつ取り出し、answer 配列に格納します。
   • キューが空になるまで繰り返し、ソートされた Node オブジェクトの val を answer 配列に入れます。

実行例

入力: {5, 6, 7, 8, 9}

1. 各整数の1の個数を計算:

   • 5（2進数: 101）→ 1の個数: 2
   • 6（2進数: 110）→ 1の個数: 2
   • 7（2進数: 111）→ 1の個数: 3
   • 8（2進数: 1000）→ 1の個数: 1
   • 9（2進数: 1001）→ 1の個数: 2

2. ソート結果:

   • 1の個数（cnt）基準で昇順にソートし、同じ場合は値自体（val）基準でソート：
   • 8 (1の個数: 1)
   • 5 (1の個数: 2)
   • 6 (1の個数: 2)
   • 9 (1の個数: 2)
   • 7 (1の個数: 3)

   結果の配列は [8, 5, 6, 9, 7] です。

Node クラスの役割

• Node クラス: 各整数の値（val）と2進数に変換したときの1の個数（cnt）を格納します。
• Comparable インターフェースの実装: compareTo メソッドを通してソート基準を定義します。cnt 値を基準にソートし、同じ場合は val 値を基準にソートします。

このアルゴリズムは 優先度キュー と 2進数演算 を利用して、整数配列を特定の条件でソートし、効率的に結果を返す方式です。

import java.util.*;

public class Solution {
    public int[] solution(int[] nums){
        int[] answer = new int[nums.length];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int num : nums) {
            int cur = num;
            int cnt = 0;
            while (cur > 0) {
                if (cur % 2 == 1) {
                    cnt++;
                }
                cur /= 2;
            }
            pq.add(new Node(num, cnt));
        }
        int idx = 0;
        while(!pq.isEmpty()){
            Node cur = pq.poll();
            answer[idx] = cur.val;
            idx++;
        }

        return answer;
    }

    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(Arrays.toString(T.solution(new int[]{5, 6, 7, 8, 9})));
        System.out.println(Arrays.toString(T.solution(new int[]{5, 4, 3, 2, 1})));
        System.out.println(Arrays.toString(T.solution(new int[]{12, 5, 7, 23, 45, 21, 17})));
    }
}
class Node implements Comparable<Node>{
    public int val;
    public int cnt;

    Node(int val , int cnt){
        this.val = val;
        this.cnt = cnt;
    }

    @Override
    public int compareTo(Node o) {
        if(this.cnt == o.cnt){
            return this.val - o.val;
        }
        return this.cnt - o.cnt;
    }
}