프로그래머스 Level 1 - 체육복.py

그리디 알고리즘을 적용하는 프로그래머스 문제,  파이썬 풀이

---

생각의 흐름

앞 순서의 학생부터, "해당 학생의 앞 학생 검사 - 양도 실패 시 뒷 학생 검사" 를 실행하여 양도가 가능하면 양도 받게 한다.

 

*놓친 점 1 : 이 주의 메세지를 보지 않아서 reserve에 포함되지만, 본인의 필요에 의해 양도가 불가능한 경우를 고려하지 않았다.

• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

-> 이후 조건을 보고 해당 케이스를 위해 각 리스트의 차집합, 교집합을 고려하였다.

---

오답 코드

def solution(n, lost, reserve):
    answer = n - len(lost)
    for who in lost:
        front = who - 1
        back = who + 1
        if front in reserve:
            reserve.remove(front)
            answer += 1
        elif back in reserve:
            reserve.remove(back)
            answer += 1
    return answer

 

def solution(n, lost, reserve):
    answer = n - len(lost)
    reserve = list(set(reserve)-set(lost))
    lost = list(set(lost)-set(reserve))
    reserve.sort()
    
    # lost 기준으로 검사 시도
    for who in lost:
        front = who - 1
        back = who + 1
            
        if front in reserve:
            reserve.remove(front)
            answer += 1
        elif back in reserve:
            reserve.remove(back)
            answer += 1
            
    # reserve 기준으로 검사 시도 
    """reserve = list(set(reserve)-set(lost))
    for give in reserve:
        front = give - 1
        back = give + 1
        
        if front in lost:
            reserve.remove(give)
            lost.remove(front)
            answer+=1
            
        elif back in lost:
            reserve.remove(give)
            lost.remove(back)
            answer+=1  """
    return answer

 

여러 시도 모두 일부 통과, 일부 불통과 ..

사실 위에 나열한 조건을 제외하고 어떤 반례 때문인지 정확하게는 파악이 안 된다.

for loop 로직은 정답코드도 다를 바가 없고, set 처리와 answer 개수 세는 부분이 달려졌기 때문에,

두 번째 오답에서는 반례 문제가 아니고 잘못된 집합처리 + 초기 answer 개수를 잘못 센 문제로 추정한다.

로직 정리는 깔끔하게 하기 .. !! 

---

정답 코드

def solution(n, lost, reserve):
	
    # 양도가 필요한 학생 = 잃어버린 학생 - 여분을 가져온 학생 / 잃어버렸지만 여분을 챙겨오지 않은 학생
    to_give = set(lost)-set(reserve)
    
    # 양도 가능한 학생 = 여분을 가져온 학생 - 잃어버린 학생 / 여분을 챙겨왔으며, 잃어버리지 않은 학생
    can_give = set(reserve)-set(lost)
    
    # 양도 받은 학생 수 초기 설정 0
    gived=0
    
    for who in to_give:
        if who-1 in can_give:
            can_give.remove(who-1)
            gived+=1
        elif who+1 in can_give:
            can_give.remove(who+1)
            gived+=1
            
    # 총 학생 - 양도가 필요한 학생 (=양도 시작 전, 스스로 체육복 입을 수 있는 학생 수) + 양도 받은 학생 수 
    return n-len(to_give)+gived