TopCoder SRM307 Div2 250Pts

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

ブーツ屋がN個の左足用ブーツと右足用ブーツの出荷を工場から受け取った。各ブーツは整数の値で同じサイズであるとき、適切なペアになる。各ブーツは1つのペアにしか属することはできない。ブーツ屋の人はN組の適切なペアを作りたいと思っている。ただ、幸いにも工場はサイズの異なるブーツは交換すると言ってくれた。さて、left[]とright[]という左と右足用のブーツのサイズが与えられたとき、交換しなければならないブーツの組の最小数を求めよ。

私の解答はこちら。

import java.util.Arrays;

public class BootsExchange {

 public int leastAmount(int[] left, int[] right) {
  int posL = 0;
  int posR = 0;
  int nMatch = 0;
  Arrays.sort(left);
  Arrays.sort(right);
  while( true ){
   if( posL == left.length || posR == left.length ) break;
   if( left[posL] == right[posR] ){ // 適切な組
    nMatch++;
    posL++;
    posR++;
   }else if( left[posL] < right[posR] ){
    posL++;
   }else{
    posR++;
   }
  }
  return left.length-nMatch;
 }

}

得点は206.98/250、中央値もほぼ同じ約207点。両足のブーツのサイズをソートしたのちに、先頭から探索し、未探索のブーツのサイズが一致すればマッチしたと言えるし、合わなければ小さい方のブーツのサイズを上げる(=ソート済なのでインデックスを1増やす)ようにすればよい。探索の終了条件は左右どちらかの靴が最後まで探索を終えたときである。