알고리즘/프로그래머스문제풀이

[Python/프로그래머스] 체육복_그리디

개발자 덕구🐾 2022. 6. 15. 21:06
728x90

 

 

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

 

코딩테스트 연습 - 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번

programmers.co.kr

 

 


 

 

그리디 : 

결정을 해야 할 때 그 순간 최적의 해를 선택하며 최종 해답에 도달한다.

그 순간 가장 좋지만, 전체적으로는 아닐 수도있기에 검증이 필요하다.

 

 

 

 

이 문제의 핵심은 왼쪽 학생 먼저 확인하는 것이다. 

 

 

 

 

 

왼쪽을 먼저 확인하고 체육복을 주는 것이 더 많은 아이들이 체육복을 입을 수 있다. 

 

그 이유는 왼쪽 부터 set을 확인하기 때문이다.

오른쪽 먼저 확인한다면 왼쪽은 다른 사람이 확인할 기회가 없다.

하지만 왼쪽부터 확인해서 준다면 못받은 오른쪽 학생은 나머지 set을 돌면서 다음 학생이 체육복을 줄수도있다. 

 

참고블로그에 가면 예시와 함께 설명이 나와있다. 

 

 

 

 

이렇게 오른쪽 먼저 확인하면 테케에서 틀린다. 

왼쪽 (i-1)을 먼저 확인하여 remove해야한다. 

 

 

 

 

 

 

 

코드 : 

 

def solution(n, lost, reserve):
    set_reserve = set(reserve) - set(lost)
    set_lost = set(lost) - set(reserve)
    
    for i in set_reserve : # 체육복을 빌려줄 수 있는 친구들을 돌면서
        if i-1 in set_lost : # 왼쪽에게 빌려줄 수 있다면 
            set_lost.remove(i-1)
        elif i+1 in set_lost : # 오른쪽 친구에게 빌려줄 수 있다면
            set_lost.remove(i+1)
        
    return n - len(set_lost)

 

 

 

 

 

복습하면서 좀 다르게 푼 코드 :

 

def solution(n, lost, reserve):
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)
    
    for i in range(1,n+1) :
        if i in reserve_set :
            if i-1 in lost_set :
                lost_set.remove(i-1)
            elif i+1 in lost_set :
                lost_set.remove(i+1)
    return n - len(lost_set)

 

 

 

 

배운 점 :

 

 

1.  set을 이용하면 차집합을 구할 수 있다.

set은 중복을 허용하지 않으며 순서 개념이 없다.

 

 

 

 


 

 

참고 블로그 : 

 

https://rain-bow.tistory.com/30

 

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

- 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어

rain-bow.tistory.com

 

 

 

복습 : 

 

20220619

20220622

✅ 20220624

✅ 20220626

반응형