プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

Javaで自分の作ったクラスに順序を入れる方法(Comparator編)(CodeFestivalあさぷろMiddle B問題)

1日で2つの記事。
いっぱい学んで偉いぞ自分。

というわけで、本番中は解けなかった、CodeFestivalあさぷろMiddleの問題Bについて書きます。


さて、この問題は、(各人の好む枕の一番小さい値(=本文中のxi)を"下限"、一番大きい値(=本文中のyi)を"上限"と書きます)
1.各参加者を、下限が低い順にならべる
2.枕を、高さの低い順にならべる
3.枕を低い順に見ていって、下限がその枕高以下の人の、上限を覚えていく。そして、その枕を下限的に使える人の中で、上限的にも使える人の内、上限が最も低い人にその枕を割り当てる。
というアルゴリズムで解けそうです。
これの実行には、1.で、
人の上限と下限をセットで覚えて、下限の小さい順にソートする
という操作が必要です。これは今までの僕には出来ませんでした。

しかし今回!ついに出来るようになりました。というわけで、やり方を説明していきます(参考にしたページはコチラ)。

まず、新しくpersonというクラス(型)を作りました。内容はこんな感じ。

class person{
  int minHeight;
  int maxHeight;
}

どシンプルですね。person型は、整数を2つ持ちます。それは好みの枕の下限と上限を表します。

そしてperson型の配列を生成します。それは

    person[] persons = new person[n];

で出来ます。
そして、人の情報を読み込んでいくのは、次のようにします。少し面倒ですが、毎回"new"を使って、新しいpersonのインスタンスを生成しなければなりません。

    for(int i = 0; i < n; i++){
      person newperson = new person();  //ここが面倒ですね
      newperson.minHeight = sc.nextInt();
      newperson.maxHeight = sc.nextInt();
      persons[i] = newperson;
    }

そしてそして、このpersonを並び変えるときに使う、比較関数を作る必要があります。
その実態がコチラ。

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;
    if(p1.minHeight < p2.minHeight){
      return -1;
    }else if(p1.minHeight > p2.minHeight){
      return 1;
    }
    return 0;
  }
}

Comparatorというクラスをimplementします。
その中にcompareという関数を書きます。
注意ですが、このcompare関数の引数はObject型のもの2つです。ここの引数をperson型にしていて、ずっとつまっていました。ややこしい。
そしてこのcompare関数で、負の値を返した場合はo1 < o2、正の場合はo1 > o2を意味します。

自然順序を入れるというやり方もあるそうなのですが、今回はやっていません。そのうちやります。そのうちだよ、そのうち。
(追記:自然順序の方もやってみました→Javaで自分の作ったクラスに順序を入れる方法(Comparable編))


このようにnewCompクラスと定義するとこのcompare関数に従ってperson型の配列をソートするという操作はこう書けます。

    Arrays.sort(persons, new newComp());

ここにもnewが必要です。ここに一番詰まりました。んもう。
これでついに、自分が作った型の配列をソートすることができました。
いぇいいぇい。進歩です。

あとは、PriorityQueue(以前学びました)を使ってやっていくだけです。余裕!

というわけで、今回の説明は以上です。
最後に、この問題の解答コードを書いておきます。解くアルゴリズムはこの記事内の頭で説明したものです。

import java.util.*;

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;
    if(p1.minHeight < p2.minHeight){
      return -1;
    }else if(p1.minHeight > p2.minHeight){
      return 1;
    }
    return 0;
  }
}


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, new newComp());

    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);
  }
}
広告を非表示にする