[프로그래머스 lv 1] 체육복

사용 언어 - Python3

문제 - 체육복

프로그래머스

 

 

 

정답

그리디 알고리즘 (정답 맞춘 여부 X)

1. 여벌의 체육복이 있는 학생도 체육복을 도난 당했을 수도 있다.

2. 양쪽 학생이 모두 빌려줄 수 있다면, 왼쪽 학생을 우선적으로 빌려준다.

def solution(n, lost, reserve):
    # 여벌이 있는 학생도 체육복을 도난 당했을 수도 있다. 
    # => 본인이 사용해야 하기 때문에, 다른 학생에게 체육복 빌려줄 수 없다.
    set_reserve = set(reserve) - set(lost)
    set_lost = set(lost) - set(reserve)
    
    for r in set_reserve:
        # 양쪽 학생이 모두 빌려줄 수 있다면, 왼쪽 학생에게 먼저 부여
        if r-1 in set_lost:
            set_lost.remove(r-1)
        # 왼쪽 학생이 없을 경우, 오른쪽 학생이 빌려줄 수 있는 지 확인
        elif r+1 in set_lost:
            set_lost.remove(r+1)
    
    return n-len(set_lost)

탐욕법 = 그리디 알고리즘

최적해를 구하는 데 사용되는 근사적인 방법

그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식

 

 

레퍼런스

• 좋은 풀이

[Python] 프로그래머스 - 체육복

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부