(C#) 다단계 칫솔 판매

코딩테스트 연습 - 다단계 칫솔 판매 | 프로그래머스 스쿨

프로그래머스

 

내용적으로 어려운건 없는 구현 문제인것같다.

주어진 조건대로 착실하게 구현만 하면 된다.

다만 최적화에서 조금 애를 먹었다.

 

처음 작성한 코드는 시간초과로 통과하지 못했다.

문제는 agents를 저장하는 자료구조였다.

처음에는 배열로 설정했는데, 배열에서 일일이 이름을 찾는 부분에서 시간이 너무 걸렸다.

그래서 Dictionary<string, Agent>로 구조를 바꿨다.

 

배열은 원하는 값을 찾기 위해서 O(n)의 시간이 걸리지만, Dictionary는 해쉬를 사용하므로 O(1)만에 원하는 값을 찾을 수 있다.

 

두번째는 foo의 재귀 호출 문제였다.

next가 1 미만인 경우에는 더이상 parent.foo를 호출하지 않아도 되는데, 이를 간과했다. 결과적으로 쓸모없는 호출스택이 늘어나는 문제가 생겼다.

 

코드

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string[] enroll, string[] referral, string[] seller, int[] amount) {
    int[] answer = new int[enroll.Length];
    Dictionary<string, Agent> agents = new Dictionary<string, Agent>();
    // Agent 생성
    for(var i = 0; i < enroll.Length; i++){
        agents[enroll[i]] = new Agent(enroll[i]);
    }
    // Agent.parent 설정
    for(var i = 0; i < referral.Length; i++){
        if(referral[i] != "-"){
            agents[enroll[i]].SetParent(agents[referral[i]]);
        }
    }
    // 합산
    for(var i = 0; i < seller.Length; i++){
        var current = agents[seller[i]];
        current.foo(100 * amount[i]);
    }
    // 결과
    for(var i = 0; i < enroll.Length; i++){
        var current = agents[enroll[i]];
        answer[i] = current.Amount;
    }
    return answer;
}

public class Agent{
    private string name;
    private Agent parent;
    private int amount;

    public Agent(string name){
        this.name = name;
    }

    public void SetParent(Agent parent){
        this.parent = parent;
    }

    public string Name{
        get{ return name; }
    }

    public Agent Parent{
        get{ return parent; }
    }

    public int Amount{
        get{ return amount; }
    }

    public void foo(int amount){
        var next = (int)(0.1 * amount);
        this.amount += amount - next;
        if(this.parent != null && next > 0){
            this.parent.foo(next);
        }
    }
}
}

결과