2021 Dev matching
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/77486
내가 생각한 문제 풀이
[시도1]
enroll을 돌면서 dict형태로
소개받은 사람 = [소개한(직전)사람, 소개한(직전의 전)사람, ...]
이런식으로 우선 만들어 둔 뒤
seller를 돌면서 해당하는 사람에 맞게 dict에서 찾아서 타고 올라가는 식으로 배당금 계산
포기한 이유 : dict형태로 소개한 사람 트리를 만들기 위해서 재귀를 사용해야 할 것 같은데 재귀 형태의 함수를 만들 수가 없었다.
[시도2]
dict에 각자 바로 위의 부모 노드만 저장해두고,동시에 money를 다루는 dict 생성
반복문/함수 사용해서 부모가 "center"일 때까지 타고 올라가면서 배당
시간 / 결과 / 패착
소요 시간 : 1:44 - 2:37
결과(정확도) : 10/13 *오답 : 시간초과
recursion이 너무 많이 돌아서 시간초과가 떴다.
단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.
문장을 그냥 넘어갔기 때문인데, 1원 미만인 경우 그냥 부모를 찾는 과정을 종료하면 된다.
문제 해설
굳이 부모의 부모의 부모를 한 딕셔너리에 정리할 필요 없이 바로 위의 부모만 알아도 문제를 풀 수 있었다.
tree(key:자식 value:부모), money(key:자식 value:배당금) dictionary를 생성하고,
각 dictionary에 대해 send함수를 진행한다.
만약 위로 올려보낼 돈이 1원보다 작다면 함수를 종료하고, 그렇지 않고 동시에 부모 노드가 있다면 함수를 다시 호출하여 진행한다.
코드
from collections import defaultdict
import math
import sys
sys.setrecursionlimit(100000)
def sendmoney(sender, amount):
send = math.floor(amount * 0.1)
money[sender] += amount - send # 받은 총액에서 보낼분량 빼고 내 지갑에 넣음
if send < 1:
return 0
parent = tree[sender] # 부모 노드 찾음
if parent == "center": # 부모 노드가 끝인 경우 그냥 끝냄
return 0
else: # 부모노드가 끝이 아닌 경우
sendmoney(parent, send)
def solution(enroll, referral, seller, amount):
answer = []
global tree
tree = defaultdict(str)
global money
money = defaultdict(int)
for idx, e in enumerate(enroll):
if referral[idx] == "-":
tree[e] = "center"
money[e] = 0
else:
tree[e] = referral[idx]
for idx, s in enumerate(seller):
sendmoney(s, amount[idx]*100) # 함수 실행
for e in enroll:
answer.append(money[e])
return answer추가 공부
트리 구조를 코드로 표현하는 방법(알고리즘)
트리 : 방향성이 있고, acyclic한 그래프 계층적인 구조를 표현
비선형 자료구조 : 일렬로 나열하기 힘들고 자료의 순서가 불규칙해서 연결 관계가 복잡한 구조(그래프/트리)
자료구조 : 선형구조, 비선형구조, 파일구조
1) 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식
2차원 배열에 각 노드가 연결된 형태를 파악
0과 1로 표현할 수 있다.
메모리 측면 : 모든 관계를 저장하므로 불필요하게 낭비
2) 인접 행렬(Adjacency List) : 리스트를 사용하는 방식
각 노드가 연결된 형태를 기록하는 방식
2차원 리스트를 사용해서 구현 가능
n번째 노드에 연결된 노드들을 이차원 리스트 안에 저장한다.
메모리 측면 : 연결된 정보만을 저장하므로 효율적
속도 측면 : 연결된 데이터를 하나씩 확인 느림
재귀 함수 짜는 방법 (알고리즘)
나중에 해보는 수밖에 ..
enumerate 함수 (파이썬)
temp = ['hi','hello','starbucks']
for i, letter in enumerate(temp):
# i: index letter: 인자recusion 문제 (파이썬)
import sys
sys.setrecursionlimit(10000)tip for me
한글로 분기마다 어떤 일을 하는지 주석 달아놓으면 스스로 생각정리하기 좋다
