99클럽 코테 스터디 20일차 TIL + 프로그래머스 탐욕 그리디

 

 

- 오늘의 학습 키워드 : 그리디(탐욕)

- 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42862
- 공부한 내용 본인의 언어로 정리하기

def solution(n, lost, reserve):
    answer = 0
    # 여벌 체육복을 도난당한 학생을 먼저 처리
    reserve_set = set(reserve) - set(lost)
    lost_set = set(lost) - set(reserve)
    # 여벌 체육복을 빌려줄 수 있는 순서를 위해 정렬
    reserve = sorted(reserve_set)
    lost = sorted(lost_set)   
    
    for k in reserve:
        if k in lost:
            lost.remove(k)
            reserve.remove(k)
                
    for k in reserve: #여벌있는 학생들 추가
        if k-1 in lost:
            lost.remove(k-1)
        elif k+1 in lost:
            lost.remove(k+1)
    answer = n - len(lost)            
    
    return answer

- 오늘의 회고
 이 문제는 이미 풀어봤던 문제라 간단하게 주석으로 

문제 풀이를 대신하게씀 하... 그리디 문제 빡세다 깊이탐색이랑 그리디는 다시 개념을 공부해봐야될 것 같다

문자열수준일떄가 좋았지ㅜㅜ

 

- 문제 풀이

 

• 여벌 체육복을 도난당한 학생 처리:
  • reserve_set = set(reserve) - set(lost)는 여벌 체육복을 가지고 있지만 도난당하지 않은 학생들의 집합을 만듭니다.
  • lost_set = set(lost) - set(reserve)는 도난당했지만 여벌이 없는 학생들의 집합을 만듭니다.
• 여벌 체육복을 빌려줄 수 있는 순서 준비:
  • reserve와 lost를 정렬합니다. 이는 빌려주는 순서를 정하기 위함입니다.
• 여벌 체육복을 가진 학생이 잃어버린 경우 처리:
  • 만약 여벌 체육복을 가지고 있는 학생이 잃어버렸다면, 그 학생은 자신에게 체육복을 사용할 수 있으므로 lost와 reserve에서 제거합니다.
• 체육복을 빌려주기:
  • 여벌 체육복을 가진 학생이 앞뒤 번호의 학생에게 빌려줄 수 있는지 확인하고, 가능한 경우 lost 리스트에서 해당 학생을 제거합니다.
• 최종적으로 체육 수업에 참여할 수 있는 학생 수 계산:
  • 전체 학생 수에서 여전히 체육복이 없는 학생 수를 빼서 체육 수업에 참여할 수 있는 학생 수를 구합니다.