프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
코딩테스트 연습
기초부터 차근차근, 직접 코드를 작성해 보세요.
programmers.co.kr
문제
https://programmers.co.kr/learn/courses/30/lessons/72416
코딩테스트 연습 - 매출 하락 최소화
CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는
programmers.co.kr
내가 작성한 코드
from collections import defaultdict
import sys
def crew_and_leader(team, leader):
crews = [] if leader != 1 else [1]
leaders = []
for crew in team[leader]:
if crew in team:
leaders.append(crew)
else:
crews.append(crew)
return crews, leaders
def get_min_sales(sales, team, team_selected, leader, dp):
crews, leaders = crew_and_leader(team, leader)
num_crews, num_leaders = len(crews), len(leaders)
select = []
not_select = []
for l in leaders:
if dp[leader][l][True] == -1:
dp[leader][l][True] = sales[l] + get_min_sales(sales, team, True, l, dp)
select.append(dp[leader][l][True])
if dp[leader][l][False] == -1:
dp[leader][l][False] = get_min_sales(sales, team, False, l, dp)
not_select.append(dp[leader][l][False])
# crew
if team_selected:
min_crew = 0
else:
min_crew = min([sales[i] for i in crews]) if num_crews != 0 else sys.maxsize
choose_crew = min_crew + sum(not_select)
# leader
num_not_selected = sum([1 for i in range(num_leaders) if not_select[i] < select[i]])
if num_leaders == 0:
choose_leader = sys.maxsize
elif num_not_selected == num_leaders:
nw_min_val = sys.maxsize
for sel in range(num_leaders):
crnt = select[sel]
for non in range(num_leaders):
crnt += not_select[non] if non != sel else 0
nw_min_val = min(nw_min_val, crnt)
choose_leader = nw_min_val
else:
choose_leader = sum([min(select[i], not_select[i]) for i in range(num_leaders)])
return min(choose_crew, choose_leader)
def solution(sales, links):
sales = [-1] + sales
team = defaultdict(list)
dp = defaultdict(defaultdict)
for leader, crew in links:
team[leader].append(crew)
dp[leader][crew] = defaultdict()
dp[leader][crew][True] = -1
dp[leader][crew][False] = -1
return get_min_sales(sales, team, False, 1, dp)
- 나눠 생각해야할 문제
- leader가 참가된 상태인지 / 참가되지 않은 상태인지
- 우리 팀 소속이 팀원인지 / 팀장인지
- 트리
- 루트가 주어짐
- 루트부터 단방향으로 탐색 가능
- DP
- 선택에 따라 서브트리의 최소매출을 중복 계산
- leader / 팀원 / 선택에 따른 memoization
다른 사람이 작성한 코드
"""Solution code for "Programmers 72416. 매출 하락 최소화".
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72416
- Solution link: http://www.teferi.net/ps/problems/programmers/72416
"""
import functools
def solution(sales, links):
@functools.lru_cache(maxsize=None)
def min_sales(node, should_include_root):
children_sum = sum(min_sales(c, False) for c in children[node])
sales_including_root = sales[node] + children_sum
if should_include_root:
return sales_including_root
sales_without_root = children_sum + min(
(min_sales(c, True) - min_sales(c, False) for c in children[node]),
default=0)
return min(sales_including_root, sales_without_root)
children = [[] for _ in sales]
for a, b in links:
children[a - 1].append(b - 1)
return min_sales(0, False)
- 경이롭다
- 내가 하고싶은 로직과 이 분의 로직이 똑같다고 생각한다
- 그런데 다른 사람의 코드임에도 내가 작성한 코드보다 더 빨리 이해된다
- 여러 다른 사람들의 코드를 살펴보면서, 이 문제는 짧은 코드로 만들 수 없구나 생각
http://www.teferi.net/ps/problems/programmers/72416
매출 하락 최소화 [테페리넷]
www.teferi.net
기억해야할 것
- @functools.lru_cache(maxzie=None)
- 함수에 대한 파라미터와 결과를 캐싱하여 DP를 간편하게 구현할 수 있다
- min(list, default=0)
- list가 비었을 때 min 사용이 안됐는데 default를 옵션으로 줄 수 있었다
'코딩테스트' 카테고리의 다른 글
[프로그래머스][KAKAO_BLIND][2018] 캐시 (0) | 2021.09.01 |
---|---|
[프로그래머스][KAKAO_BLIND][2018] 프렌즈4블록 (0) | 2021.09.01 |
[프로그래머스][KAKAO_BLIND][2020] 외벽 점검 (0) | 2021.09.01 |
[프로그래머스][KAKAO_BLIND][2018] 뉴스 클러스터링 (0) | 2021.09.01 |
[프로그래머스][KAKAO_BLIND][2018] 추석 트래픽 (0) | 2021.09.01 |