99클럽 코테 스터디 9일차 TIL | 다단계 칫솔 판매 반례 (Python)

문제 링크 : 프로그래머스 다단계 칫솔 판매

 

항상 자신의 추천인에게 판매 대금의 10%를 떼줘야하는 다단계 기업이 있다.

10% 수수료 계산시 소수점을 버림하는 규칙이 있다.

아래와 같은 4개의 배열이 주어질 때, 주어진 각 멤버의 수익을 계산해서 배열로 반환해야한다.

빠르게 부모 노드를 찾을 수 있는 자료구조를 고안하는것과, 반례를 찾는것이 중요한 문제였다.

 

예시 케이스

조직도가 [ 사장 - A - B - C ] 형태일 때, 인풋은 아래와 같이 주어진다.

 

조직도는 아래 형태로 주어지고

	[0]	[1]	[2]
enroll (멤버이름)	A	B	C
referral (추천인)	- (사장은 "-" 로 표시한다.)	A	B

 

칫솔 판매 실적은 아래처럼 주어진다. 칫솔은 하나에 100원으로 고정이다.

	[0]	[1]	[2]
seller (판매 담당자)	A	C	A
amount (칫솔 판매 갯수)	1	2	1

 

이번 케이스의 경우, 함수 반환값으로 [182, 18, 180] 를 내놓으면 정답이다. 계산 과정은 아래를 참고하자.

	사장	A	B	C
A가 100원 벌어옴	+10	+90
C가 200원 벌어옴	+0 (소수점 버림)	+2	+18	+180
A가 100원 벌어옴	+10	+90
반환값	(사장은 반환 안함)	182	18	180

 

 

구현 아이디어

멤버 이름을 사용할 일이 많으므로 Map 자료구조를 dictionary로 구현하여 빠르게 관련 정보를 찾기로 했다.

총 두개의 맵을 사용했다.

- ref_map : 멤버 이름을 key로, 멤버의 추천인을 value로 가진다.

- benefit_map : 멤버 이름을 key로, 멤버의 여태까지 수입을 value로 가진다.

 

get 메서드로 예외처리를 할 수도 있었지만,

모든 멤버키가 한번 이상 조회되는 것이 보장되었으므로 zip을 활용하여 모든 키를 초기화해주었다.

def solution(enroll_input, referral_input, seller, amount):
    # - 예외처리
    enroll = ["-"] + enroll_input # ["-", "A", "B", "C"]
    referral = ["-"] + referral_input # ["-", "-", "A", "B"]

    # map 초기화
    benefit_map = {name : 0 for name in enroll} # {"-": 0, "A": 0 ...}
    ref_map = {key : value for key, value in zip(enroll,referral)} # {"A": "-", ...}

 

또한 소수점 내림은 별도 라이브러리 사용 없이 정수 나눗셈 연산자로 대체하였다. 

9 / 10  # 0.9
9 // 10 # 0

 

반례

 

각 판매원의 판매 실적을 모두 더해버린 다음, 총액에 대해 수수료를 계산하려는 잘못된 생각(ㅜ)을 할 수 있다.

이 경우 소수점 내림 규칙 때문에 각 판매 건수에 대해 수수료를 걷었을 때 보다 수수료 금액이 커지게된다.

예시를 한번 보자.

 

<Case 1. 말단사원 D가 100원을 20번 벌어왔을 때>

	사장	A	B	C	D
D가 100원 벌어옴	+0	+0	+1	+9	+90
D가 100원 벌어옴	+0	+0	+1	+9	+90
... 18번 반복
반환값	0	0	20	180	1800

 

<Case 2. 말단사원 D가 한번에 2000원을 벌어왔을 때>

	사장	A	B	C	D
D가 1000원 벌어옴	0	2	18	180	1800
반환값	0	2	18	180	1800

 

따라서 아래처럼 매 판매건수에 대해 수수료를 분배하는 작업을 반복해야한다.

 

def solution(enroll_input, referral_input, seller, amount):
    PRICE, HEAD_NAME = 100, "-"
    enroll = [HEAD_NAME] + enroll_input # - 예외처리
    referral = [HEAD_NAME] + referral_input # - 예외처리
    
    # 1. 빠른 멤버 정보 조회를 위한 Map 자료구조 선언
    benefit_map = {name: 0 for name in enroll}
    ref_map = {key: value for key, value in zip(enroll, referral)}
    
    def pay_commission(child_name, parent_name, benefit):
        if child_name == parent_name or benefit == 0:
            return # 다단계 꼭대기에 왔거나 0원이면 재귀 종료
        
        commission = benefit // 10
        benefit_map[child_name] += (benefit - commission) # 주의 : int(benefit * 0.9)로 대체하면 틀림
        
        # 수수료를 다시 상위 추천인에게 전달
        pay_commission(parent_name, ref_map[parent_name], commission)
    
    # 2. 각 판매 건수에 대해 수수료 징수
    for i, name in enumerate(seller):
        pay_commission(
            child_name = name, 
            parent_name = ref_map[name], 
            benefit = PRICE * amount[i]
        )
    
    # 3. enroll 순서대로 수익 출력
    return [benefit_map[name] for name in enroll_input]

---

오늘의 회고

소수점 오차를 간과하여 구현보다 더 긴 시간을 디버깅에 쏟았다.

문제를 풀 당시에는 전혀 감도 안잡혀서 점점 최적화를 없애고 문제를 그대로 따라하는 식으로 접근했는데,

다행히 이러한 접근이 효과가 있어서 좋은 점수를 받을 수 있었다.

그러나 이 방식은 테스트 케이스가 충분하지 않은 경우 전혀 소용이 없다.

따라서 항상 문제의 제한 조건이 허락하는 한도에서, 가장 극한 상황을 연출하는 테스트 케이스를 작성해서 오차가 적은 알고리즘을 만들 수 있도록 하자.

내일은 정답률이 정말 낮은 문제에 도전해서 스스로 반례를 만들어내는 연습을 더 해봐야겠다.