[python3] 이것이 취업을 위한 코딩 테스트다 - 거스름돈 (ch.3 그리디)

내돈내산~~

참고) 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 기반으로 작성된 문제와 코드입니다. 
따라서 문제는 자세하게 적지 않고, 간단한 설명과 제 코드만 올리겠습니다.

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

예제 3-1) 거스름돈

카운터에서 사용할 돈) 500원, 100원, 50원, 10원짜리 무한개 존재가 존재.
N원의 돈을 거슬러줄 때, 최소의 동전 갯수

 

<문제풀이>

N은 정해져 있지 않고 동전의 갯수도 무한 개이다. 따라서 그냥 N의 값을 가장 큰 동전(500원)으로 나누면,  몫이 동전의 갯수가 될 것이다. 그리고 남은돈에 다음으로 큰 동전을 나누어주고,,,, 이 과정을 반복하면 되겠다.

 

<내가 작성한 코드>

프로그래머스에서 def 함수로 작성하기 떄문에 그 형식대로 작성해 보았다.

count = 0

def change_money(N, wallet):
    total = 0
    for coin in wallet:
        count = N // coin
        N = N - (coin*count)
        total += count
        
    print("거스름돈으로 받을 총 동전 갯수는? : %d 개" %total)

출력)

N = 1260
wallet = [500, 100, 50, 10]

#결과 출력
change_money(N, wallet)

 

<예시 코드와 비교>

나는 count 와 total 변수 두 개를 사용해서 count를 계속 선언하고 ,최종적으로 total에 더해주면서 최종 값을 구했다.
하지만 책의 예시를 보면, count += n // coin 이렇게 함으로써 그냥 count에 몫만 계속 더해 나갔다. 

고로 내 코드에서는 변수를 줄이고, 코드를 한줄이라도 더 줄임으로써 시간복잡도를 줄일 수 있을 것이다.  아직 부족한점이 많다 ㅠ^ㅠ

 

은근 헷갈리는 것 !! ★★

• %: 나머지 반환
• // : 몫 반환