[PROGRAMMERS] 2021 Dev-Matching: 다단계 칫솔 판매 Python

사실 이 문제는 자신 있게 풀었다가 완전히 오답이 나서 내 접근 자체가 틀렸단 걸 느껴 질문하기를 통해 힌트를 보고 풀었다. 질문하기를 보니 나처럼 접근했다가 답을 틀린 사람이 많았던 것 같다.

우선 문제를 간단히 설명하자면 다단계 조직원들의 수입을 리스트로 반환하는 문제이다. 

다단계 칫솔 판매 (출처 : 프로그래머스)

이런 식으로 다단계 조직원들의 구조가 이루어져 있을 때, 자신이 개당 100원짜리의 칫솔을 판매하거나 자신의 자식이(추천받은 사람) 수익을 얻어 자신이 수익을 받는다면 90%를 내가 가지고 10%를 자신의 부모(추천인)에게 보내주어야 한다.

여기서 나는 두가지 실수를 하였다.
1. 모든 자식노드의 수입이 정해진 후 자신의 수입을 정한다(트리의 후위 순회)
-> 틀린 이유 : 수입을 받을 때마다 부모에게 보내주어야 함(10%를 보내줄 때 내림 값(문제 조건)이 달라져서 답이 틀림)
2. 부모 노드를. index를 통해 찾으려고 함
-> 시간제한이 명시 안되어 있어서 시간을 너무 사용함

두 가지 실수를 통해 풀었는 방법은 트리를 구현하여, 트리의 후위 순회로 자식의 수입을 정 학고 부모의 수입을 정하는 방법을 사용했다. 틀린 코드를 잠깐 보자면

다단계 칫솔 판매 틀린코드

위에 설명한 것처럼 접근방식이 틀렸고, 시간을 많이 사용하는. index를 남발하여 시간 복잡도도 많이 사용했다.

다행히? 제출을 했을 때, 싹 다 오답이 나와서 이 방식이 잘못됐다는 것을 깨닫고 금방 새로 풀 수 있었다.
새로 푼 문제는 위에 실수 두 가지를 다른 방법으로 접근했다.
1. 수입이 발생할 때마다, 부모에게 10%의 금액을 보내준다.(내림의 계산이 다르게 됨)
2. 부모와 수입을 딕셔너리로 정리하여 시간 복잡도를 줄였다.

코드로 보자면,

정답 풀이

이렇게 풀었다.

부모 정보와 수입정보를 딕셔너리로 저장해 놓고, 수익을 낸 사람들을 돌면서 자신의 부모가 '-'이거나 부모에게 줄 수입이 없을 때까지 부모에게 돈을 보내주었다.

풀고 나니 어려운 문제는 아닌 것 같지만, 처음 시도했던 방법이 모두 틀렸을 때 멘붕이 와 서 너무 쉽게 힌트를 찾아보았던 것 같다. 알고리즘 문제를 풀 때, 내가 생각한 방법이 안된다면 다른 방법으로 생각하고, 풀어보는 연습을 해 봐야 할 것 같다. 

오늘도 파이팅!

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/77486