<aside> 💬 lv0, 그리디

최대 분산 투자

문제 설명

여러 투자 기회가 주어졌을 때, 제한된 자본으로 가장 많은 투자를 할 수 있는 함수를 작성해주세요. 각 투자 기회는 투자 금액과 투자처로 되어 있습니다. 모든 투자는 독립적이며, 투자 금액의 합은 주어진 자본을 초과할 수 없습니다.

예를 들어, 자본이 50만원이고 투자 기회가 [(20만원, 'A기업'), (30만원, 'B기업'), (40만원, 'C기업')]으로 주어진다면, 최대 분산 투자는 ['A기업', 'B기업']입니다.

제한 사항

"최대 분산 투자" 문제에 대한 수정된 입출력 예와 입출력 설명은 다음과 같습니다:

입출력 예

입력 (투자 기회, 자본) 출력 (분산 투자 기업 리스트)
[(200000, 'A기업'), (300000, 'B기업'), (400000, 'C기업')], 500000 ['A기업', 'B기업']
[(100000, 'A기업'), (200000, 'B기업'), (300000, 'C기업')], 500000 ['A기업', 'B기업']
[(50000, 'A기업'), (70000, 'B기업'), (120000, 'C기업')], 180000 ['A기업', 'B기업']

입출력 설명

첫 번째 예시에서 자본은 500,000원이며, 가장 많은 기업에 투자하기 위해 'A기업'과 'B기업'에 투자하는 것이 최적의 선택입니다. 'A기업'에 200,000원, 'B기업'에 300,000원을 투자하여 총 2개의 기업에 투자합니다.

</aside>

😺 풀이 1. 리스트

def solution(data):
    investments, capital = data **#1 초기 변수 설정**
    investments.sort(key=lambda x: x[0]) **#2 정렬**

    selected_companies = [] **#3 빈 리스트 생성**
    for cost, company in investments: **#4 모든 요소 순회**
        if capital >= cost:
            selected_companies.append(company)
            capital -= cost

    return selected_companies **#5 결과 반환**

단계별 풀이 전략

  1. 초기 변수 설정

    입력값 data를 investments, capital로 나누어 할당한다. 각각 투자기회(회사), 자본에 해당한다.

  2. 정렬

    투자기회를 오름차순으로 정렬한다.

  3. 빈 리스트 생성

    selected_companies라는 변수에 빈 리스트를 생성한다.

  4. 모든 요소 순회

    1. 투자기회를 cost, company로 나누어 순회한다.
    2. if capital >= cost → 만약 자본이 투자기회의 자본값보다 크거나 같다면, selected_companies리스트에 투자기회의 회사명을 추가한다.
    3. 그리고 자본에서 투자기회의 자본값을 뺀 후 재할당을 한다.

  5. 결과 반환

    반복문, 조건문을 거친 selected_companies리스트를 반환한다.

풀이 2. filter() 함수

def solution(data):
    asset = data[1]
    lst = sorted(filter(lambda x: x[0] <= asset, data[0]))
    ret = [] **#1 초기 변수 설정 및 정렬**
    for money, company in lst: **#2 모든 요소 순회**
        if asset < money:
            break
        asset -= money
        ret.append(company)
    return ret **#3 결과 반환**

단계별 풀이 전략

  1. 초기 변수 설정 및 정렬

    변수 asset에 data[1], 자본을 할당한다.

    filter함수로 자본보다 같거나 작은 값들만 걸러주고 이를 오름차순으로 정렬한다. 그리고 빈 리스트 ret을 선언해준다.

  2. 모든 요소 순회

    각 행을 money, company로 순회한다.

    1. 만약 자본보다 투자기회의 자본값이 크다면 반복문을 탈출(break).
    2. 아니라면 자본에서 투자기회의 자본값을 뺀 후 자본asset에 재할당해준다.
    3. 투자기회의 회사명을 리스트ret에 추가한다.

  3. 결과 반환

    모든 반복문과 조건문을 거친 리스트ret을 반환한다.

알아둬야 할 개념

함수 filter()

break