•
문제 설명 : 초콜릿의 가격 목록과 제공된 돈이 있다.
◦
이 돈을 활용하여, 가장 적은 가격으로 2개의 초콜릿을 먹었을 때 거스름돈을 반환한다.
◦
만약 2개의 초콜릿을 사먹을 수 없다면, 안사먹고 돈을 그대로 반환한다.
•
풀이 방법
◦
처음에는 prices를 sort 로 정렬하여 진행했었다.
▪
O(NlogN)으로 풀렸다.
◦
가장 작은 값과 그 다음으로 작거나 같은 값만 필요하기 때문에, 굳이 모든 요소를 정렬할 필요가 없다고 생각했다.
▪
정렬된 배열은 추가적으로 사용하지 않기 때문이다.
◦
그래서 순회하여 값만 구하여 사용하는 방식을 택하였다.
•
시간복잡도 :
•
성공 코드
class Solution:
def buyChoco(self, prices: List[int], money: int) -> int:
first_price = min(prices[0], prices[1])
second_price = max(prices[0], prices[1])
for i in range(2, len(prices)):
# 가장 작은 값이 새로 나올 경우
# 기존 가장 작은 값은 두번째 값으로 이동
# 가장 작은 기존 가격과 동일해도, 새로운 요소이기 때문에 동일하게 작업
if prices[i] <= first_price:
second_price = first_price
first_price = prices[i]
elif prices[i] < second_price:
second_price = prices[i]
minimum_two_chocolates_prices = first_price + second_price
return money - minimum_two_chocolates_prices if minimum_two_chocolates_prices <= money else money
Python
복사
