[프로그래머스] 다단계 칫솔 판매 [Level 3] (python 파이썬)

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

프로그래머스

 

 

 

 

 

 

 

def solution(enroll, referral, seller, amount):
    d = {}
    graph = {}
    for i in range(len(referral)):
        d[enroll[i]] = referral[i]
        graph[enroll[i]] = 0
    s = []
    for i in range(len(amount)):
        s.append([seller[i], amount[i]* 100])

    for i in s:
        graph[i[0]] += int(i[1] * 0.9)
        이자 = int(i[1] * 0.1)
        부모 = d[i[0]]
       
        while 부모 != "-":
            if 이자*0.1 < 1:
                graph[부모] += 이자
                break
            graph[부모] += 이자 - int(이자*0.1) 
            이자 = int(이자 * 0.1)
            부모 = d[부모]
    ans =[]
    for i in enroll:
        ans.append(graph[i])
    return ans

 

 

 

 

---

문제 정리

 

 

 

다단계 트리....ㄷㄷ

 

위 그림처럼 center 부터 시작하는 트리가 있다.

 

즉, center가 가장 높은 부모가 되는 트리이고,

 

자식 노드가 번 수익의 10%씩 부모에게 전달되는 원리이며,

 

부모에게 전달된 10% 중 10%를 부모의 부모에게 전달하며, 

 

10% 가 1보다 작을 시, 전달하지 않는 규칙이다. 

 

 

 

 

 

 

---

문제 접근 사고 과정

 

 

 

규칙을 잘 읽어보면, 다단계의 수익 분배는 seller 부터 시작된다.

 

즉 시작은 seller 이며, 부모로 올라가면서 수익의 10% (이하 이자라고 함) 처리를 하면 된다.

 

즉, 수익 분배 과정을 차분히 따라가며 구현하는 문제이다.

 

 

 

생각해야 될 점..?

문제를 풀기 위해서 고려해야 할 점이 무엇일까? 머리에 생각나는데로 적어보자...

 

1. 부모와 자식 관계 (부모를 따라 올라가야 하므로, 부모와 자식 관계를 고려해봐야 한다.)

2. 수익의 처리  (seller 에게 처음 수익이 주어졌을 때, 즉, 초기 처리를 고려해봐야 한다.)

3. 이자의 처리  (부모를 따라 올라가는 이자의 처리, 반복되는 과정의 처리를 고려해야 한다.

4. 소수점 처리 (10% 처리를 해야 하므로, 소수점의 문제가 발생할 여지가 있다.)

 

이 정도가 생각이난다. 

 

 

 

입력의 전처리

 

문제를 풀기 쉽게 입력을 우리가 원하는 형식으로 처리해보자.

 

부모와 자식의 관계는 부모만 알면 된다.

문제를 풀면서 자식이 누군지는 알 필요가 없다. 

따라서 자식을 key로 부모를 value로 가지는 딕셔너리를 사용한다.

 

for i in range(len(referral)):

        d[enroll[i]] = referral[i]

        graph[enroll[i]] = 0

++ 추가로 정답을 담고 있는 graph 까지 전처리 해둔다.

 

 

판매 정보도 전처리 해두자.

    s = []

    for i in range(len(amount)):

        s.append([seller[i], amount[i]* 100])

 

 

 

 

문제 처리

 

seller에 대해서 

    for i in s:

 

 

본인은 수익의 90%를 가져간다.

 graph[i[0]] += int(i[1] * 0.9)

 

 

남은 10%는 부모에게 주어야 한다

 

이자와 부모의 전처리

  이자 = int(i[1] * 0.1)

        부모 = d[i[0]]

.

 

 

부모가 없을 때까지 이자를 넘겨주어야한다.

while 부모 != "-":

 

 

 

만약 이자의 10% 가 1원보다 작으면, 본인이 다 가져가고, 반복을 멈춘다.

 if 이자*0.1 < 1:

                graph[부모] += 이자

                break

 

 

 

 

이자가 충분하다면, 이자의 10%를 다시 부모에게 주고, 남는 이자를 본인이 가져간다.

 graph[부모] += 이자 - int(이자*0.1)

            이자 = int(이자 * 0.1)

            부모 = d[부모]

 

 

 

 

정답 출력!

    ans =[]

    for i in enroll:

        ans.append(graph[i])

    return ans

           

 

 

 

 

---

추가 아이디어

이자의 10%를 빼고 가져간다는 로직을 (이자*0.9) 로 표현하면 안된다

 

만약 이자가 12원이라면, 본인은 11원을 가져가고, 부모에게 1원을 주어야 한다.

하지만 12*0.9 = 10.8 이므로, 0.9를 곱하면 본인이 10원을 가져가고, 1원을 부모에게 넘겨주게 된다.