[코딩테스트] 2021 Dev-Matching: 웹 백엔드 개발자(상반기)다단계 - 칫솔 판매

---

문제

 

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

프로그래머스

 

칫솔을 판매하는 다단계 업체에서 위쪽으로 10%씩 떼어줘야 할 때, 각 사람이 가질 돈을 구하는 문제

 

칫솔 하나당 100원이며, 10%를 떼어주는 금액이 1원 미만이면 떼어주지 않아도 된다.

 

seller, amount의 묶음, 즉 판매량에 seller가 중복해서 들어있을 수 있다. 하지만 seller의 판매 금액을 합쳐서 한번에 계산하면 안된다. 따로따로 계산했을 때 10%가 1원 미만이 되고, 합쳐서 계산했을 때 10%가 1원 이상일 수 있기 때문이다.

 

 

---

전략

 

01. Tree

 

 각 사람을 노드라고 생각하고 윗 사람과의 연결 관계를 지어준 뒤 판매량을 하나씩 계산하면 될 것 같다.

 

 

---

풀이

 

class Node:
    def __init__(self, name, head):
        self.name = name
        self.head = head
        self.money = 0
    
    def __repr__(self):
        return str(self.name) + str(self.money)

def solution(enroll, referral, seller, amount):
    node_minho = Node("minho", None)
    
    enroll_nodes = {}
    for j in range(len(enroll)):
        if referral[j] == "-":
            enroll_nodes[enroll[j]] = Node(enroll[j], node_minho)
        else:
            enroll_nodes[enroll[j]] = Node(enroll[j], enroll_nodes[referral[j]])
    
    for name, earning in zip(seller, amount):
        earning = earning * 100
        node = enroll_nodes[name]
        while node is not None:
            my_money = 0
            up_money = 0
            if earning * 0.1 < 1:
                my_money = earning
                node.money += my_money
                break
            else:
                up_money = int(earning * 0.1)
                my_money = earning - up_money
                
            node.money += my_money
            earning = up_money
            node = node.head

    result = []
    
    for name in enroll:
        result.append(enroll_nodes[name].money)
        
    return result

 

각 사람을 나타내는 노드를 만들어 준다. 각 노드에는 그 사람의 이름 name, 윗 사람의 노드 head, 그 사람이 받은 돈 money를 각각 넣어준다.

 

node_minho = Node("minho", None)

 

다단계 업체의 수장인 민호의 노드를 만들어준다. 민호는 윗사람이 없으니 None으로 만들어준다.

 

 

enroll_nodes = {}
for j in range(len(enroll)):
    if referral[j] == "-":
        enroll_nodes[enroll[j]] = Node(enroll[j], node_minho)
    else:
        enroll_nodes[enroll[j]] = Node(enroll[j], enroll_nodes[referral[j]])

 

각 노드의 레퍼런스를 저장할 enroll_nodes 딕셔너리를 만들고, referral이 "-"일 경우 head를 민호 노드로, 아닌 경우는 각각의 윗사람 노드를 가리키도록 해서 Tree관계를 완성한다.

 

 

for name, earning in zip(seller, amount):
    earning = earning * 100
    node = enroll_nodes[name]
    while node is not None:
        my_money = 0
        up_money = 0
        if earning * 0.1 < 1:
            my_money = earning
            node.money += my_money
            break
        else:
            up_money = int(earning * 0.1)
            my_money = earning - up_money

        node.money += my_money
        earning = up_money
        node = node.head

 

각 seller와 그 판매량인 amount를 하나씩 읽어가면서 본인이 가질 돈과 위로 보낼 돈을 계산하면 된다. while문을 통해 더이상 떼줘야 할 node가 없을 때까지 반복하는데, 이때 earning * 0.1 즉 위로 보내야할 돈이 1보다 작을 경우, 더이상 위로 보내줘도 의미 없기 때문에 break로 반복문을 끝내주는 것이 중요하다. 여기서 계속 틀림..

 

 

for name in enroll:
    result.append(enroll_nodes[name].money)

 

마지막으로 enroll 순서에 따라 가지는 돈을 출력해주어야 하므로 해당하는 각 노드의 돈을 result 리스트에 하나씩 append해서 출력해주면 된다.

 

 

 

---

다른 사람의 풀이

 

1. 해시

def solution(enroll, referral, seller, amount):
    graph,ans = {},{e:0 for e in enroll}

    for e,r in zip(enroll,referral): graph[e]=r

    for s,a in zip(seller,amount):
        money = a*100
        rate = money//10
        ans[s] += money-rate
        x = graph[s]

        while x != "-":
            if rate==0: break
            ans[x] += rate-rate//10
            rate//=10
            x = graph[x]

    return list(ans.values())

 

그냥 딕셔너리로 풀어버렸다. 윗사람과의 관계는 graph 딕셔너리에 저장하고, 각자 가지는 돈은 ans 딕셔너리에 각각 저장해 Node를 만드는 것과 같은 효과를 냈다.