[プログラマー]スポーツウェア|貪欲法|Python

問題の説明

昼食の時間に盗まれ、一部の学生の運動服が盗まれた.幸いなことに、余分な運動服を貸したい学生がいます.学生の番号は体格順で、前の番号の学生か後ろの番号の学生の運動服しか貸せません.例えば、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

I/O例説明

例1
1番学生は運動服を2番学生に貸し、3番学生または5番学生は運動服を4番学生に貸し、5人は体育の授業を受けることができる.
例2
3番の学生は運動服を2番の学生か4番の学生に貸して、4人の学生は体育の授業を受けることができます.

プール1)

    # 중복값이 없다는 제한 때문에 원소의 값이 unique 하기위해 set사용 # lost = [1,1,2] reserve = [3,3,4] 불가능
    # 여벌이있는(reserve)학생도 도난 당했을 수도 있다는 것은 lost 값에 reserve값이 공통적으로 존재할 수 있다 # lost =[1,2,3],reserve[3,4,5]
    # 3번 학생은 여벌을 빌려줄 수 없음 , 따라서 lost에 reserve와 같은 값이있다면 reserve에서 제외시킴

def solution1(n,lost,reserve):
    set_lost = set(lost) - set(reserve) # 잃어버렸지만 여벌이 있는 학생은 제외
    set_reserve = set(reserve) - set(lost) # 여벌이 있지만 잃어버려서 빌려줄 수 없는 학생은 제외

    for i in set_reserve: # 여유분이 있는 학생들을 뽑음
        if i - 1 in set_lost: # 왼쪽 학생이 잃어버렸는지 판단후 
            set_lost.remove(i-1) # 잃어버렸다면 빌려주고 잃어버린 학생 리스트에서 삭제
        elif i + 1 in set_lost: # 오른쪽 학생이 잃어버렸는지 판단후
            set_lost.remove(i+1) # 잃어버렸다면 빌려주고 잃어버린 학생 리스트에서 삭제
    return n-len(set_lost) # 전체학생에서 체육복을 빌리지 못한 인원 만큼 뺀 후 리턴

プール2)コードは短いが,更新後に4つのテストケースが合格できなかった.

def solution2(n, lost, reserve):
    reserve = set(reserve)
    for size in [0, 1, -2]:
        lost = set(map(lambda x : x+size, lost))
        reserve, lost = reserve - lost, lost - reserve

    return n - len(lost)

プール3)🤔

def solution4(n, lost, reserve): 
    _reserve = sorted([r for r in reserve if r not in lost]) # 제한사항을 set 자료형으로 안하고 not in 컴프리헨션으로 처리
    _lost = [l for l in lost if l not in reserve]
# reserve에 sorted를 하지않으면 테스트케이스 18번 20번이 통과 되지않음
    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)