はい。前の記事(Javaで自分の作ったクラスに順序を入れる方法(Comparator編))ではやらなかったと書いた、Javaにおいて、『作ったクラスに自然順序を入れる』というのに挑戦してみたらすんなり出来たので、それについて書こうと思います。
ちなみに、僕が競技プログラミングとかそういうのを勉強しているときは、たいてい自分の研究が嫌になっているときです。
まぁでも、逃避がまた別の勉強になっているのは、無気力にダラダラするよりはいいかと思って書いています。来週も教授の前でしょんぼりすることになるでしょうけども。
さて、題材にしたのは、CodeFestivalあさプロMiddle問題Bです。
ここでは、各人が好みの枕の高さについて下限値と上限値を持っているという設定ですね。人を下限値でソートするため、新しくクラスを作り、それらに順序を与えるクラスを作りました。
具体的には、personというクラス(int型の値、minheightとmaxheightを持つ)と、newCompというComparaterをimplementsしたクラスを作りました。
コードはこんな感じでした(前の記事から一部変更しています)。
class person{ int minHeight; int maxHeight; } class newComp implements Comparator{ public int compare(Object o1, Object o2){ person p1 = new person(); person p2 = new person(); p1 = (person)o1; p2 = (person)o2; return p1.minHeight - p2.minHeight; } }
こうした後に、
person[] persons = new person[n]; for(int i = 0; i < n; i++){ person newperson = new person(); newperson.minHeight = sc.nextInt(); newperson.maxHeight = sc.nextInt(); persons[i] = newperson; } Arrays.sort(persons, new newComp());
という風に、personの配列とnewCompのインスタンスをsort関数に渡せばOKというものでした。
ちなみに、compare関数は、
・返り値が負の数なら、 『1つ目の引数 < 2つ目の引数』
・返り値が正の数なら、 『1つ目の引数 > 2つ目の引数』
を表します。
今回の『自然順序を入れる』というのが出来ると、上のようにクラスを2つ作らず、1つのクラスを作るのみで同じ動作ができます(参考にしたページはコチラ)。
さて、さっそくどんなコードか書きますね。
class person implements Comparable{ int minHeight; int maxHeight; public int compareTo(Object other){ person otherperson = (person)other; return minHeight - otherperson.minHeight; } }
compareToという名前にしなければいけないことに注意して下さいね。
これは、前回のやり方よりスマートな感じがしますね。
ちなみにひっかかったところとしては、
・compareToの引数はObject型にしなければならない
・compareTo関数はpublicにしなければいけない
というところでしょうか。
また、compareTo関数は
・返り値が負の数の場合は引数の方が大きく
・返り値が正の数の場合は引数の方が小さい
というのを表します。
このようにすると、person型の配列であるpersonsを引数にして
Arrays.sort(persons);
と書くだけで、ソートが完了します。スマートですね。
ただ、例えばperson型に対して、色んな順序でソートしたいときは、この方法では無理で、前回やったComparatorをimplementsしたクラスを2つ作るしかないのかな、と思っています。
型の中に勝手に順序が入ってますもんね。
前回のComparatorを使う方法は、冗長な部分がある代わりに、そこでの自由度も高い、という感じでしょうか。
さて、今回は以上です。
最後に、一応この自然順序の方で問題を解いたときのコードの全体を貼り付けて終わりにします。
import java.util.*; class person implements Comparable{ int minHeight; int maxHeight; public int compareTo(Object other){ person otherperson = (person)other; return minHeight - otherperson.minHeight; } } public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); person[] persons = new person[n]; for(int i = 0; i < n; i++){ person newperson = new person(); newperson.minHeight = sc.nextInt(); newperson.maxHeight = sc.nextInt(); persons[i] = newperson; } Arrays.sort(persons); int[] makukras = new int[m]; for(int i = 0; i < m; i++){ makukras[i] = sc.nextInt(); } Arrays.sort(makukras); int count = 0; int lookingIndex = 0; PriorityQueue<Integer> priQue = new PriorityQueue<Integer>(); for(int i = 0; i < m; i++){ //その枕を(下限だけ見て)使えそうな人を、どんどんPriorityQueueに入れていく。 //どこまでの人を見たかも覚えとく(このチェックをクリアしてQueueに入った人達は、これ以降の枕についても下限的には使えるハズであるから、再考しなくてよい)。 while(lookingIndex < n && makukras[i] >= persons[lookingIndex].minHeight){ priQue.add(persons[lookingIndex].maxHeight); lookingIndex++; } //キューが空なら、この枕を使える人はいない if(priQue.isEmpty()){ continue; } //下限的にクリアした人の中で、上限が一番小さい人を見ていく。 //この枕を上限的にも使える人に出会うまでみていく while(!priQue.isEmpty() && makukras[i] > priQue.peek()){ priQue.poll(); } //キューが空なっちゃったなら、この枕を使える人はいない if(priQue.isEmpty()){ continue; }else{ count++; priQue.poll(); } } System.out.println(count); } }