Programmers Greedyジャージ

[欲張り法(Greedy)]スポーツウェア

Link: https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3

問題の説明

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

<制限>

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

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

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

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

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

I/O例

n lost reserve return
5 [2, 4][1, 3, 5] 5
5 [2, 4][3] 4
3 [3][1] 2

Code

def solution(n, lost, reserve):
    
    # 1. lost와 reserve에 같은 수가 있다면 제거
    for x in lost:
        if x in reserve:
            lost.remove(x)
            reserve.remove(x)
    
    # 2
    answer = n - len(lost)

	# 3
    while True:
        temp = answer
        for x in lost:
            if x+1 in reserve and x-1 not in reserve:
                answer += 1
                reserve.remove(x+1)
                lost.remove(x)
            elif x-1 in reserve and x+1 not in reserve:
                answer += 1
                reserve.remove(x-1)
                lost.remove(x)
        if answer == temp: break
    
    # 4
    for x in lost:
        if x-1 in reserve:
            answer += 1
            reserve.remove(x-1)
        elif x+1 in reserve:
            answer += 1
            reserve.remove(x+1)
    
    return answer

コードの説明

まず、紛失した人が余分な運動服を持っているかどうかを判断しなければならない.余計なことなら、なくしたら、あの人は自分のジャージを着ればいい.loss&reserveリストから削除します.

正解の数は、紛失した人がどれだけ着ているかを探すので、答えは「総人数-紛失した人の数」です.

私はこのドアを繰り返します.前の人にしか借りられないなら、前の人に借ります.后の人にしか借りられないなら、その人は后の人に借ります.貸し出しのたびに、スタンバイ・ユーザー・リストが更新されます.そのため、最初から見直す必要がある.これ以上借りる人がいなければ、whileドアを出ます.

今、失った人の中で、前の人や後ろの人にお金を借りることができれば、答えを増やして正解を求めます.

コードエラー

TestCase 7号にエラーがありました.明らかにアルゴリズムに問題があり、漏れがある.運動服を借りる方法の前後で一番いい方法を選ぶべきです.そうしないと、答えの数が違います.
*エラーの検出
間違いは意外に簡単だ.コード説明#1号にジャージを余す学生がいなくなった場合、貸すことができず、自分で解決しなければなりませんが、この部分ではfor loopのloss関数でlossインデックスを削除すると正解が違います.loss関数をlost copyに保存し、lost copyメソッドを使用してloss関数の項目を削除すると、問題を解決できます.

#변경사항
lost_copy = lost.copy()
for x in lost_copy:
        if x in reserve:
            lost.remove(x)
            reserve.remove(x)

Code Output(Screenshot)

より良いコード

count = 30
def rec_(k,M,selected,lost,reserve):
    temp_lost = lost.copy()
    global count
    if k == M:
        for i in range(0,M):
            #만약 0이면 앞쪽 친구가 체육복이 없는지 확인 후 빌려준다.
            if selected[i]==0:
                if reserve[i]-1 in temp_lost:
                    temp_lost.remove(reserve[i]-1)
                    
            #만약 1이면 뒷쪽 친구가 체육복이 없는지 확인 후 빌려준다.    
            elif selected[i]==1:
                if reserve[i]+1 in temp_lost:
                    temp_lost.remove(reserve[i]+1)
                    
        if len(temp_lost) <= count:
            count = len(temp_lost)
        
    else:
        for cand in range(0,2):
            selected[k] = cand
            rec_(k+1,M,selected,lost,reserve)
            selected[k] = -1


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

    #여벌옷 가져온 학생이 체육복을 잃어버리는 경우
    lost_copy = lost.copy()
    for i in range(len(lost_copy)):
        if lost_copy[i] in reserve:
            lost.remove(lost_copy[i])
            reserve.remove(lost_copy[i])
                
    print(lost,reserve)

    M = len(reserve)
    selected = [-1 for _ in range(M)]

    rec_(0,M,selected,lost,reserve)
    answer = n - count
    return answer