スポーツウェア(Programmers 42862)

🧑‍💻 質問する

昼食時間に盗まれ、一部の学生の運動服が盗まれた.幸いなことに、余分な運動服を貸したい学生がいます.学生の番号は体格順で、前の番号の学生か後ろの番号の学生の運動服しか貸せません.例えば、4番の学生は3番か5番の学生にしか運動服を貸すことができません.運動服がないと授業を受けられないので、適当に運動服を借りて、できるだけ多くの学生に体育の授業をさせなければなりません.

生徒全体の数n、盗まれたジャージの生徒の番号の並びがなくなったり、複数セットのジャージをつけた生徒の番号の並び備蓄がパラメータとして与えられた場合は、解答関数を書いて体育の授業を受けられる生徒の最低価格が戻ってくるようにしてください.

せいげんじょうけん

全体の生徒数は2名以上30名以下であった.

運動服を盗まれた生徒数は1名以上n名以下で重複番号はない.

着以上のユニフォームの学生数は1名以上n名以下で、重複番号はありません.

着以上の運動服を持っている学生だけが他の学生に運動服を貸すことができます.

着以上の運動服を持っている学生は盗まれたかもしれません.このとき、この学生は1枚の運動服だけが盗まれたと仮定し、1枚の運動服しか残っていないため、他の学生に運動服を貸すことができない.

🧑‍💻 解決策

カテゴリから分かるように、これはグリディアルゴリズムです.

比較的簡単な問題

🧑‍💻 貪欲法

貪欲法は主に最適解を求めるために用いられる.

ですが、このアルゴリズムはちょうどいいとは言えません.その原因は,最適解が得られないことが多いからである.

🧑‍💻 失敗コード

入力したlossリストに直接触れたため、テストケースの実行に失敗しました.また,時間的複雑度はn(O^2)であるため,あまり良いコードではない.

def solution(n, lost, reserve):
    answer = 0
    for res_stu in reserve:
        for lo_stu in lost:
            if (res_stu - 1) == lo_stu or (res_stu + 1) == lo_stu:
                answer += 1
                lost.remove(lo_stu)
    answer = n - len(lost)
    return answer

🧑‍💻 コード#コード#

def solution(n, lost, reserve):
    answer = 0

    los = [l for l in lost if l not in reserve]
    res = [r for r in reserve if r not in lost]

    for r in res:
        if r-1 in los:
            los.remove(r-1)
        elif r+1 in los:
            los.remove(r+1)
    answer = n - len(los)

    return answer

🧑‍💻 総評

貪欲法は、聞いたことのないアルゴリズム名にすぎない.

しかし、私が解題方法を見たとき、それは私が知っている解題方法にすぎません.

問題は簡単ですが、私も時間の複雑さの問題があり、入力したリストに直接追加して、問題があったようです.

のリストがあれば、一度再生する方法もいいようです.

悩みも大切ですが、多くの接触問題は私にとって必要です.