[プログラマー]ユニホーム


📌 問題の説明


昼食の時間に盗まれ、一部の学生の運動服が盗まれた.幸いなことに、余分な運動服を貸したい学生がいます.学生の番号は体格順で、前の番号の学生か後ろの番号の学生の運動服しか貸せません.例えば、4番の学生は3番か5番の学生にしか運動服を貸すことができません.運動服がないと授業を受けられないので、適当に運動服を借りて、できるだけ多くの学生に体育の授業をさせなければなりません.
すべての学生の数n,ジャージを盗まれた学生の番号の並びloss,複数のジャージを持った学生の番号の並びreserveをパラメータとした場合,解関数を書いて体育の授業を受けられる学生の最上位値を返してください.

せいげんじょうけん

  • 全体の生徒数は2名以上30名以下であった.
  • 運動服を盗まれた生徒数は1名以上n名以下で重複番号はない.
  • 着以上のユニフォームの学生数は1名以上n名以下で、重複番号はありません.
  • 着以上の運動服を持っている学生だけが他の学生に運動服を貸すことができます.
  • 着以上の運動服を持っている学生は盗まれたかもしれません.このとき、この学生は1枚の運動服だけが盗まれたと仮定し、1枚の運動服しか残っていないため、他の学生に運動服を貸すことができない.
  • I/O例


    nlostreservereturn5[2, 4][1, 3, 5]55[2, 4][3]43[3][1]2

    💡 に答える


    コード#コード#

    import java.util.*;
    class Solution {
        public int solution(int n, int[] lost, int[] reserve) {
            int answer = n - lost.length;
            for(int i = 0; i < reserve.length; i++){
                for(int j = 0; j < lost.length; j++){
                    if(reserve[i] == lost[j]){
                        reserve[i] = -1;
                        lost[j] = -1;
                        answer++;
                        break;
                        }
                 }
            }
            
            for(int i = 0; i < reserve.length; i++){
                for(int j = 0; j < lost.length; j++){
                    if(reserve[i] == -1){
                        break;
                    }else if((reserve[i]-1) == lost[j] ||
                      (reserve[i]+1) == lost[j] ){
                        lost[j] = -1;
                        answer++;
                        break;
                    }
                }
            }
            
            return answer;
        }
    }

    説明:


    運動服を借りる前に体育の授業を受けることができる学生数は、すべての学生数から盗まれた学生の値を差し引く.(answer = n - lost.length)
    複数のスポーツウェアでも、自分が盗まれた場合は他の学生に貸すことができないため、reserveとlossが同じ要素があれば、この2つの要素の値に-1を代入します.
    ここで-1を代入するのはreserveにlossを貸さないためである.
    ユニホームは自分より1つ小さいか1つ大きい方が貸してくれるので、reserve要素に1または1を加算してlossにすると、loss要素に-1が代入され、体育の授業が受けられる学生数の回答に1が加算されます.(reserve要素の値が-1の場合はスキップします.)
    ここでlost-1を代入するのは,重複貸し出しを避けるためである.loss(2,3,5),reserve(2,4),4を3に貸すと,5を貸すことができない.

    ポスト


    私は最初、この問題の最終的な答えを導く過程で、学生数(n)から失われた学生数(loss.length)を取り除くべきだと思っていたので、lossの要素値を取り除く方向に近づいた.これにより,配列値を削除できるチェーンテーブルや配列リストが用いられ,問題がより複雑になる.解くときに答えが見つからないので、方法を変えました.reserveが貸出できない場合、代入-1とreserve要素値が-1でない場合にのみ、要素値の削除と同じ効果を考慮します.これでずっと簡単です.