프로그래머스 코딩테스트 고득점 Kit_탐욕법(Greedy)_체육복

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

• "여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다."
  => 다음 조건을 만족시키기 위해 set자료형을 이용하여 lost와 reverse에 공통으로 존재하는 원소를 제거

• 체육복을 빌려 줄 수 있는 사람의 왼쪽사람부터 탐색하고, 도난당했다면 체육복을 빌려주고 lost에서 해당 사람 제거. 만약 도난당하지 않았다면 오른쪽 사람을 탐색하며 다음과 같은 과정을 반복하는 로직으로 reverse 반복

• 결국 마지막에는 lost에는 체육복을 빌리지 못한 사람만 남게 됨
  => return (전체 학생수 - 체육복을 빌리지못한사람)
  => return n - len(lost)

구현 코드👇

def solution(n, lost, reserve):
    #중복 제거하는 전처리
    reserve, lost = set(reserve) - set(lost), set(lost) - set(reserve) 
    
    for student in reserve:
        if student - 1 in lost:
            lost.remove(student - 1)
        elif student + 1 in lost:
            lost.remove(student + 1)
        
    return n - len(lost)