TopCoder SRM415 Div2 250Pts

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

あなたの趣味は郵便消印を集めることである。N個の異なる消印があり、0からN-1まで番号が付けられている。それらの価値はprices[]という整数型の配列で与えられており、添字iが消印iの価値を表すものとする。あなたの目標はできるだけ異なる種類の消印を集めることである。既に持っている消印はhave[]という整数型配列で与えられている。また、初期状態では所持金0の状態とする。消印を売り、お金を得て異なる消印を買うということができる。集められる消印の種類数の最大値を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class CollectingUsualPostmarks {

 public int numberOfPostmarks(int[] prices, int[] have) {
  int value = 0;
  for( int i=0 ; i<have.length ; i++ ){
   value += prices[have[i]];
  }
  Arrays.sort(prices);
  int count = 0;
  int current = 0;
  for( int i=0 ; i<prices.length ; i++ ){
   current += prices[i];
   if( current > value ) break;
   count++;
  }
  return count;
 }

}

得点は191.82/250、問題文を読み替えて、全部売って安い方から買っていくと問題を置き換える発想の転換すると非常に見通しが良くなります。