다단계 칫솔 판매

 

https://school.programmers.co.kr/learn/courses/30/lessons/77486

프로그래머스

문제요약:

번돈의 10퍼센트를 추천인에게 상납해야하는 다단계가 있다, 각 인원들이 번돈을 구하시오

 

소요시간:

20분 +a

난이도3

 

코딩:

from collections import defaultdict
import math
	
def solution(enroll, referral, seller, amount):
	stride = dict()
	result = defaultdict(int)
	
	def cal(name,money):
		#돈이 0 이라면 더이상 돌필요가 없음
		while money!=0:
			#10퍼센트로 절삭
			ten_per = math.floor(0.1*money)
			#90퍼센트는 내가 먹기
			result[name] += money - ten_per
			#마지막이라면 10프로도 내가 먹고 끝내기
			if name == '-':
				result[name] += ten_per
				break
			else:
				name = stride[name]
				money =ten_per
	
	for en,re in zip(enroll,referral):
		stride[en] = re
		
	for sell,money in zip(seller,amount):
		cal(sell,100*money)
		
	return [result[i] for i in enroll]

 

일단 문제는 zip함수와 dict함수를 통해 내가 판돈의 90퍼센트는 내가 먹고 10퍼센트는 내 추천인이 먹고, 추천인이 없을땐 그 10프로도 맨위가 먹게(사실 enroll 엔 맨위가없기때문에 빼도됨) 했습니다. 

이때 맨처음 DFS로 짰는데 맨뒤 3개의 테스트케이스 빼고 모두 통과가 나왔습니다.  

이때 틀림이 아닌 런타임 에러가 나왔는데 DFS를 사용했을때, 다른 모든 테스트 케이스에선 정답이 나오고, 특정케이스에서만 실패가 아닌 런타임 에러가 나왔다면 함수 반복 제한을 생각해보아야 합니다. 그리고 이를 BFS로 바꾸고 나서 시간초과 오류가 뜨게 되었습니다.

결국 혼자서 해결하지 못하고 힌트를 보았는데, amount의 범위가 100까지 이므로 많아봐야 10000원 인것이고 이를 10프로씩 때도, 결국 5계단을 올라가게 되면 돈이 0원이 되기 때문에 하는 의미가 없어지는것 이었습니다.

그래서 원래 while문에 조건이없었는데 간단히 0이되면 탈출하는 조건을 추가하여 문제를 해결하였습니다.