강의 계획 레슨 148개 중 134번째 · 고스트를 이겨라
고스트를 이겨라

캐시 없이: 물려받는 할인

왜 중요한가 "일을 되풀이하니 답을 기억하라"는 사람이든 AI든 프로그래밍에서 가장 강한 습관 중 하나예요. 때로는 그 일을 아예 되풀이할 필요가 없어요.

가게의 분류는 나무를 이뤄요: Garden은 Home 아래, Tools는 Garden 아래 등등. 마케팅 관리자는 어떤 분류에든 할인을 정할 수 있고, 더 가까운 분류가 자기 할인을 정하지 않는 한 그 아래 모든 것에 적용돼요. 결제는 한 번에 수천 개 분류의 실제 할인을 찾아봐요.

데이터

parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25}           # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]

나무를 거듭 올라가는 것에 대한 뻔한 해결책은 캐시예요. 이 문제에서는 캐시가 금지돼요. 애초에 일을 되풀이하지 않는 방법을 찾으세요.

내 차례

effective_discounts(parents, own, queries)를 쓰세요. parents는 모든 분류를 그 부모에, 최상위 분류면 None에 매핑해요(여럿일 수 있고, dict에는 특별한 순서가 없어요). own은 일부 분류를 자기 할인에 매핑해요. queries의 각 분류에 대해, 자기부터 시작해 맨 위로 가는 경로에서 own에 할인이 있는 가장 가까운 분류의 할인을, 없으면 0을 반환하세요. 규칙: 캐시나 메모 금지: functools 캐시 데코레이터 금지, "cache"나 "memo"를 포함한 이름 금지, 질의가 물을 때 답을 계산하고 지니는 것도 금지(다른 이름의 메모). 먼저 나무 전체를 훑고, 그다음 질의를 읽으세요. 예산: 분류 3,000개, 깊이 수백 단계까지의 나무, 찾기 20,000번에 대해 최대 500,000걸음(steps()).

이 레슨에서 문제를 발견했나요? 알려 주세요 · 이 레슨에 대해 묻기

이 연습은 곧 열려요

앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.