[HackerRank] Electronics Shop (전자제품상점) Implementation 문제

 

문제

당신은 새 키보드와 USB 드라이브를 구매하려고 합니다.

가게에서 각 제품에 대한 다양한 가격이 주어집니다.

당신은 제한된 예산 내에서 하나의 키보드와 하나의 USB 드라이브를 구입하려고 합니다.

가능한 한 많은 돈을 쓰고 싶지만, 예산을 초과할 수는 없습니다.

예산 내에서 키보드와 USB 드라이브를 구입할 수 있는 최대 금액을 계산하세요.

 

입력값:

• 첫 번째 줄: 예산을 나타내는 정수 b.
• 두 번째 줄: 키보드의 가격 목록을 나타내는 정수 배열 keyboards.
• 세 번째 줄: USB 드라이브의 가격 목록을 나타내는 정수 배열 drives.

 

출력값:

• 예산 내에서 키보드와 USB 드라이브를 함께 구매할 수 있는 최대 금액을 출력합니다. 
• 만약 어떤 것도 구매할 수 없다면 -1을 출력합니다.

 

예시:

입력

10
[3, 1]
[5, 2, 8]

 

출력

9

 

 

풀이

브루트 포스(Brute Force) 방법 :

• 가능한 모든 경우의 수를 모두 탐색하여 문제를 해결하는 방식
• 문제의 해답을 찾기 위해 모든 가능한 조합이나 시도를 전부 수행하는 방법
• 경우의 수가 많아지면 연산 시간이 급격히 증가하므로, 실행시간이 매우 오래 걸릴 수 있는 단점

def getMoneySpent(keyboards, drives, b):
    max_spent = -1  # 초기 값은 -1로 설정 (예산 내에서 구매 불가능할 경우를 대비)
    
    # 모든 키보드와 USB 드라이브 조합에 대해 예산을 넘지 않는 최대값을 계산
    for k in keyboards:
        for d in drives:
            if k + d <= b:
                max_spent = max(max_spent, k + d)
    
    return max_spent

# 예시 실행
b = 10
keyboards = [3, 1]
drives = [5, 2, 8]

print(getMoneySpent(keyboards, drives, b))  # 출력: 9

 

itertools.product(곱집합)를 이용한 풀이

from itertools import product

def getMoneySpent(keyboards, drives, b):
    # 모든 가능한 조합 생성
    combinations = list(product(keyboards, drives))
    # [(3, 5), (3, 2), (3, 8), (1, 5), (1, 2), (1, 8)]

    # 예산 내에서 구매할 수 있는 최대 금액 찾기
    max_spent = -1
    for k, d in combinations:
        total = k + d
        if total <= b:
            max_spent = max(max_spent, total)
    
    return max_spent