Electronics Shop 파이썬 풀이 및 해설

오늘은 해커랭크 알고리즘 퀴즈 중 Electronics Shop를 풀어보겠습니다.

파이썬으로 간단히 풀고 간단한 해설 추가하겠습니다.

문제

한 사람이 주어진 예산으로 구입할 수있는 가장 비싼 컴퓨터 키보드와 USB 드라이브를 결정하려고합니다. 키보드 및 USB 드라이브의 가격표와 예산이 주어지면 구매 비용을 찾으십시오. 두 항목을 모두 구매할 수없는 경우 -1을 반환합니다.

설명

예를들어 예산이 60이 주어지고 키보드 가격이 40, 50, 60 이고 USB 드라이브 가격이 5, 8, 12 일 때, 주어진 예산에서 살 수 있는 가장 비싼 조합을 알려주면 됩니다. 이 경우는 50짜리 키보드와 8짜리 USB를 58에 살 수 있습니다. 이보다 하나라도 더 비싼걸 사게되면 예산을 초과하여 불가능합니다. 그리고 주어진 돈으로 키보드와 USB를 각각 하나씩 살 수 없다면 불가능 케이스로 -1를 리턴하면 됩니다. 

그럼 풀이 부터 보고 해설하도록 하겠습니다.

풀이

def getMoneySpent(keyboards, drives, b):
    sum = -1
    for keyboard in keyboards:
        if keyboard < b:
            for drive in drives:
                if drive < b and keyboard + drive <= b and sum < (keyboard + drive):
                        sum = keyboard + drive
    return sum


if __name__ == '__main__':

    bnm = input().split()

    b = int(bnm[0])

    n = int(bnm[1])

    m = int(bnm[2])

    keyboards = list(map(int, input().rstrip().split()))

    drives = list(map(int, input().rstrip().split()))

    #
    # The maximum amount of money she can spend on a keyboard and USB drive, or -1 if she can't purchase both items
    #

    moneySpent = getMoneySpent(keyboards, drives, b)
    print(moneySpent)

해설

이 문제는 복잡하게 풀면 정말 복잡하게 풀 수도 있습니다. 여러 풀이 방법과 최적화된 풀이 방법이 많겠지만 여기서는 단순히 짜기 쉬운 코드로 작성한 점을 이해 부탁드립니다.

일단 여기서는 조합을 만들어야 합니다. 키보드 드라이브 조합을 k, d라고 할 때 각 원소들의 모든 조합을 만들어야 합니다. 이런 경우 경우의 수가 k * d 이므로 가장 간단하게 이중 for 문으로 접근하면 모든 원소의 조합을 만들고 비교해 볼 수 있습니다.

시작은 키보드로 시작해 안에 드라이브를 비교합니다. 갯수가 달라도 전혀 상관없습니다. 예산이 초과되면 안되므로 keyboard 와 drive 는 각각 예산보다 작아야 한다를 조건으로 넣어줍니다. 예산을 b로 명명하고 keyboard < b 조건을 먼저 걸었습니다.

예산보다 작고 그리고 drive와 더한 값이 예산보다 작다면 일단 구매 가능합니다. 이렇게 하나씩 하면서 예산보다는 작고, 둘을 합쳤을때 예산에 딱 맞는 조합이 최고의 조합이 될 것입니다. 따라서 예산 이하의 가장 큰수를 sum에 담으면 되는 것이죠. for문을 돌면서 예산에 가장 매핑되는 값이 sum으로 계산됩니다. 이 조건이 두번째 for문에 들어있습니다. sum의 초기값은 불가능 케이스인 -1로 주고 각 조합식이 이전의 sum보다 크면 교환합니다. 이렇게 되면 최종 값은 최대 값이 되거나 아예 불가능한 -1을 반환할 겁니다.

다만 이렇게 되면 모든 값을 모두 조회하는 성능적으로 좋은 케이스는 아닐 것입니다. 예산과 똑같은 결과가 나왔다면 사실 바로 리턴하고 끝내도 됩니다.

여기는 단순히 알고리즘만 풀이하고 있으므로 이런 방식으로 풀이를 마칩니다.

원본 퀴즈 출처 : https://www.hackerrank.com/challenges/electronics-shop/problem

깃허브에서 보기 : https://github.com/kitlexyz/algorithm/blob/master/hackerrank/electronics-shop.py