TopCoder SRM270 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について、おおまかに説明する。

スティーブは新しい車を買いたいと思っている。ただ、お金がないので、リーズナブルな安いものを好んでいる。ただ一番安い車の品質は疑問である。そこで、スティーブは車の価格一覧から3番目に安い価格の車を買うことにした。prices[]という、整数型の車の価格が入った配列が与えられる。pricesには何度も同じ価格が現れることもあるが、それは1度数えるだけとする。prices[]で3番目に安い車の価格を返す関数を作成せよ。もし、車の価格が3種類に満たない場合は、-1を返すようにせよ。

私の解答はこちら。

import java.util.Iterator;
import java.util.TreeSet;

public class BuyingCheap {

 public int thirdBestPrice(int[] prices) {
  TreeSet<Integer> ts = new TreeSet<Integer>();
  for( int i=0 ; i<prices.length ; i++ ){
   ts.add(prices[i]); // ユニークな集合の作成
  }
  if( ts.size() < 3 ) return -1; // 集合のサイズが2以下なら3番目に安い車はない
  Iterator<Integer> it = ts.iterator();
  int i = 0;
  while( it.hasNext() ){ // イテレータを利用して3番目に小さい要素を返す
   if( i==2 ){
    return it.next();
   }
   it.next();
   i++;
  }
  return -1;
 }

}

得点は136.52/250。Setの使い方の良い復習になりました。TreeSetにしておくと、集合を昇順にソートしてくれるので、そのまま問題に適用可能です。