[Python] 프로그래머스 알고리즘 고득점 Kit ✅ 탐욕법 (Greedy) (~ing)

[Level 1] 체육복

def solution(n, lost, reserve):

    # 조건 5 (본인 것 잃어버린 경우, 본인 옷으로 대체)
    set_lost = set(lost) - set(reserve) # 차집합 활용하여 공통 부분 제거
    set_reserve = set(reserve) - set(lost)
    
    # 한 명씩 옷 매칭해서 제외 (여벌 가진 3번은 2번과 4번에게만 빌려줄 수 있음 !!)
    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)

    answer = n - len(set_lost)
            
    return answer

 

[Level 2] 구명보트

• 앞에부터 50+50 이렇게 하려고 하지 말고, 20+80을 먼저 없애버리는 방식으로 풀이

def solution(people, limit):
    answer = 0
    
    # 1) 무게 순서대로 정렬
    people.sort()
    
    # 순서대로 더해서 limit 보다 넘으면 answer 값 하나 추가하면 22점 나옴
    # [다른 방식] 제일 첫 값과 마지막 값을 더했을 때, limit 보다 작으면 구출하고 리셋하는 방식
    start = 0
    end = len(people)-1
    while (start <= end):
        # 20, 80키로로 예를 들면 가능하면 둘이 한 번에 구출
        if (people[start]+people[end]) <= limit:
            start += 1
            end -= 1
        # 50, 80키로면 뒤에 있는 80키로라도 먼저 구출
        else:
            end -= 1
        answer += 1
        
    return answer

 

[Level 2] 큰 수 만들기

• 스택을 활용하자 (pop)

def solution(number, k):
    answer = ''
    
    # 숫자 리스트로 변환
    number_ = list(number) # ['1', '9', '2', '4']
    number_list = [int(i) for i in number_] # [1, 9, 2, 4]
    
    # 스택 활용
    stack = []
    for num in number_list:
        # 스택이 비어 있지 않고, 스택의 마지막 값이 num보다 작으며, k가 0보다 클 때
        while stack and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    
    # k가 0이 아닌 경우 맨 마지막 숫자부터 삭제
    if k != 0:
        stack = stack[:-k]
    
    stack_ = [str(i) for i in stack]
    answer = ''.join(stack_)
    
    return answer

 

[Level 2] 조이스틱

 

[Level 3] 섬 연결하기

 

[Level 3] 단속카메라