프로그래머스 - 체육복(python)

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

문제접근

• 체육복 여분을 갖고 있는 학생과 체육복이 없는 학생을 비교해 체육복을 갖고있는 학생을 최대한 많이 만드는 경우의 수를 구하기
• 여분을 갖고 있는 학생은 한 명한테만 빌려줄 수 있음
• 자신의 앞, 뒤 번호의 학생한테만 빌려줄  수 있음

 

실패사례

def solution(n, lost, reserve):
    #여벌의 체육복을 갖고 있는사람이 도난당했을때 문제발생
    #체육복을 갖고 있는 사람
    answer = n - len(lost)

    check = [False] * (n+1) #여분의 체육복의 여부

    for i in range(len(reserve)):
        check[reserve[i]] = True
        
    #빌릴 사람이 있는지 확인
    for i in range(len(lost)):
        for j in range(len(reserve)):
            if abs(lost[i] - reserve[j]) <= 1:
                #빌려준 친구는 또 빌려줄 수 없음
                if check[reserve[j]]:
                    check[reserve[j]] = False
                    #받은 친구는 수업을 들을 수 있음
                    answer += 1
        if answer == n:
            break
    
    return answer

두 배열을 비교해 체육복을 빌려주고 bool 배열을 활용해 이미 빌려준 학생은 또 다시 빌려줄 수 없도록 하였다.

일반적으론 문제없는데 체육복을 잃어버린 사람과 여분의 체육복이 있는 사람이 중복될때 문제가 발생했다.

 

 

정답코드

def solution(n, lost, reserve):
    #1.set을 활용해 둘 다 포함되는 애들 제거
    reserve_only = set(reserve) - set(lost)
    lost_only = set(lost) - set(reserve)
    
    #2. 여분을 기준으로 앞뒤를 확인하여 체육복을 빌려준다.
    for reserve in reserve_only:
        front = reserve - 1
        back = reserve + 1
        if front in lost_only:
            lost_only.remove(front)
        elif back in lost_only:
            lost_only.remove(back)
            
    #3. 전체 학생수에 lost_only에 남은 학생 수를 빼준다.
    answer = n - len(lost_only)
    return answer

set을 활용하여 양 배열에 중복적으로 들어있는 사람을 없앴다.

그리고 이전 코드와 달리 여분의 체육복을 가진학생의 앞뒤 번호가 lost에 있을 경우 lost에서 빼는 방식으로 구현했다.

 

참고자료

https://www.youtube.com/watch?v=yiNIJuVvSbY&list=PLlV7zJmoG4XJfK8vVL2E2NX8ej73vjNlh&index=7