[프로그래머스] 다단계 칫솔 판매 (Swift)

[프로그래머스] 다단계 칫솔 판매 (Swift)

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

코딩테스트 연습 - 다단계 칫솔 판매

이해

아래 그림과 같이 생긴 다단계 수익 구조가 있고, 판매원이 칫솔을 하나 판매할때마다 자신은 수익의 90% 를 가져가고 자신의 parent 에게 수익의 10% 를 나눠줍니다.

 

주어진 배열을 이용해 이를 반복하였을 시 판매원들이 가져가는 수익을 계산하는 문제입니다.

프로그래머스 - 다단계 칫솔 판매

얼마전에 트라이 자료구조 관련한 문제를 풀어서인지 그림을 보자마자 트라이 자료구조가 생각났습니다.

 

그래서 먼저 트라이를 구현한 후 부모 노드를 따라 올라가며 수익을 분배하는 방식으로 문제를 해결하려 했으나, 너무 복잡한 방식인것 같아서 다른 방법을 생각해보았습니다.

 

판매원의 부모를 따라 계속 올라가는 방식이기 때문에, DFS 의 개념을 이용하고자 했습니다. 판매원과 판매한 칫솔 개수가 주어졌을 때 부모의 이름이 -, 즉 루트 노드가 되기 전까지 수익을 계속 분배하는 방식입니다.

 

저는 이를 위해서 Person 이라는 구조체를 선언하여 부모 정보와 수익 정보를 담기로 했고, [판매원 이름 : 부모 구조체] 형식으로 이루어진 Dictionary 를 생성하여 부모를 빠르게 탐색할 수 있도록 하였습니다.

 

또한 수익을 분배할때 수익의 90%, 10% 를 나눠서 계산하면 소수점 때문에 생기는 오차가 있기 때문에 수익의 10% 를 먼저 계산한 뒤 전체 수익에서 이를 빼주는 방식으로 해결하였습니다.

 

문제에서 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다. 부분을 구현하지 않게 된다면 마지막 3개의 테스트 케이스에서 시간초과가 발생하기 때문에 DFS 를 종료해주어야 합니다.

코드