[99클럽 코테 스터디] 5일차 TIL - 탐욕법(Greedy), 체육복

[5일차] 탐욕법(Greedy)

 

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

프로그래머스

Solution

제한 사항에 여벌을 가져왔어도 도난을 당할 수 있다는 부분에 유의해서, 가장 먼저 이 꼬임을 해결해준다.

이후 실제로 빌려줄 수 있는 학생들을 반복문을 통해 확인해준다. -1 또는 +1 이면 빌려줄 수 있다는 조건을, 여러 경우의 수를 동시에 생각하며 복잡하게 생각하지 말자. 

def solution(n, lost, reserve):
    answer = 0
    
    # 여벌 체육복을 가져왔지만 도난당한 학생을 제거
    lost_set = set(lost) - set(reserve)
    reserve_set = set(reserve) - set(lost)
    
    # 빌려주기
    for r in reserve_set:
        if r - 1 in lost_set:
            lost_set.remove(r - 1)
        elif r + 1 in lost_set:
            lost_set.remove(r + 1)
    
    # 최종 학생 수
    answer = n - len(lost_set)
    
    return answer

* 제한 사항을 이해할 반례로는, input : 5, [4, 5], [3, 4] / output: 4 가 있다.

** 출처 by 지피티 .. 

나다어

아래는 처음 생각했던 잘못된 코드이다. 기반하여 나다어를 작성해보자면 .. ✍🏻

• 원본 배열은 건드리지 말자.
• 복사본이 있다면, 배열의 값을 바꿀 필요 없으니 따로 변수를 두지 말고 아예 삭제하여 쉽게 처리하자. 
• 단계별로 task를 쪼갠 것은 좋은 접근이었다.
• 결국 구해야 하는 것이 무엇인지 말(문장)으로 명확히 정리하고 시작하자. 오히려 해답을 이끌어내는 힌트가 된다!

def solution(n, lost, reserve):
    answer = 0
    # 그리디 문제는 정렬과 함께 쓰인다
    
    for l in lost:          # 여벌이 있었지만 도난 당한 학생들
        if l in reserve:
            lost.remove(l)
            reserve.remove(l)
            break
            
    normal = set(lost+reserve)
    answer += (n-len(normal))    # 여벌도, 도난도 아닌 학생들
       
    
    for l in lost:          # 빌릴 수 있는 학생 수 계산
        if l-1 in reserve:
            answer += 1
            reserve[reserve.index(l-1)] = False
        elif l+1 in reserve:
            answer += 1
            reserve[reserve.index(l+1)] = False
    
    
    answer += len(reserve)
    
    return answer