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

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

코딩테스트 연습 - 체육복

 

• 해설 :

총 인원, 체육복을 잃어버린 사람, 여분 체육복이 있는 사람의 배열이 주어질 때, 여분 체육복이 있는 사람은 양 옆의 사람에게 체육복을 빌려줄 수 있다. 이 때 최대한 많은 사람이 체육복을 사용하는 경우를 찾는 문제이다.

 

 

 

• 풀이 :

그리디 알고리즘을 사용하여 해결하는 문제이다. 체육복을 빌려줄 때, 왼쪽에 있는 사람부터 빌려줘야 가장 많이 빌려줄 수 있는 최적의 경우이므로 빌려줄 수 잇는 사람의 왼쪽 사람부터 검사하여 최대한 체육복을 빌려준 후 전체 길이에서 체육복이 없는 사람의 수를 빼면 된다.

 

 

 

 

def solution(n, lost, reserve):
    answer = 0
    tmpl = set(lost) - set(reserve)
    tmpr = set(reserve) - set(lost)
    for i in tmpr:
        if i-1 in tmpl:
            tmpl.remove(i-1)
        elif i+1 in tmpl:
            tmpl.remove(i+1)
            
        
    return n-len(tmpl)