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

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

문제에 또 집착을 해버려서.시간이 얼마나 날아간거지

문제 이해

트리구조 → parent(추천인)가 존재함.

• parent에게 주는 것 : “자신의 이익”의 10프로
  • 10프로 계산 과정에서 소수점이 존재하는 경우 → 내림.
• 자신의 이익 : 자신이 판매한 이익 + child가 발생시킨 이익의 10프로
• 그런데 이 때, 자신의 이익을 먼저 계산하고 분배하면 안 되는 것 같다..

  • 예시를 보았는데 1200 → 120 배분 → 12 배분 → 1 배분 (1.2니까)

    이런 경우가 생겨서..

• 문제에서 주어지는 것 : enroll , referral인데, 어차피 각 child의 바로 위 부모는 하나밖에 없다.
  • 즉 enroll[i]의 부모는 referral[i]라는 것임.
  • “-” 는 , 이 노드의 parent가 없다는 것을 의미함.
• seller는 판매원의 이름을 나열함 → 즉, 모든 enroll이 seller에 들어있지는 않을 수도 있음.
  • seller[i] 는 amount[i] 개 만큼을 판매한다.
  • seller에는 “같은이름”이 중복해서 들어있을 수 있다.
    • 그런데 어차피 각각 해야하는 것 아닌가 ?????
    • 2개를 팔았다 ⇒ 200 → 20 → 2 → 0
    • 18개를 팔았다 ⇒ 1800 → 180 → 18 → 1
    • 20개 팔았다 → 2000 → 200 → 20 → 2
    • 차이가 보이는가???? 같은 사람이 , 200원어치와 1800원어치를 팔았으니 그냥 더하면 되지 라고 생각하면 가장 위에 있는 사람이 받는 금액이 달라져 버린다.
    • 이를 해결하려고 부동소수점으로 풀었는데 → 해결법이 아니었음을 나중에 깨닳았다.
    • 그냥 seller 하나하나씩에 대한 dfs를 하는 방식으로 바꾸는게 맞다 ( 동일한 seller끼리 합해준 경우 실패가 뜨더라 )
• 칫솔 판매이익은 개당 100원

문제 풀이

처음에는 언뜻 Union find인가.. 했는데 생각해보니 그냥 바로 위의 parent만 사용해도 될 것 같았다.

일단, 사람의 이름이 주어지기 때문에 무조건 hash 자료구조를 사용할 것이다.

→ [ 사람 : 부모 ] 맵

→ [ 사람 : 금액 ] 맵

seller의 길이는 10만 이하다.

referral의 길이는 1만 이하다 → 10000 x 100000 은.... 안되겠군.

• 그럼 일단 seller를 정리해서 → 1만길이로 만들어준다 . → 이렇게 하니 틀렸다.
• skewed tree라면 ?? 그래도 → 10000 + 9999 + 9998 + .... +1 → 5천만 정도?

틀렸다 ( 시간초과 )

.... 오늘 또 문제에 좀 집착하고 있다..하루종일 이것만 풀었네.. 이러지 않기로 했는데 그게 잘 안되는듯하다;

• 🚀 💥문제조건💥amount의 범위가 100 이라는 것 → 10프로씩만 올라가고, 내림을 하기 때문에, 10000→1000→100→10→1→0 다. 그리고 0이 되는 시점부터는 더 올라가지 않고 cut을 해 주면 되기 때문에 많이 올라가도 내가 걱정했던 것 처럼 skewed tree를 따라서 쭉 올라가는 경우는 없었던 것이다.
  • 💥→ cur 에 대한 제약조건을 걸어줘야 한다. 💥 dfs 시에는 cut할 조건을 잘 생각해 줘야 한다...
    • 왜냐하면 cur이 0 이어도 트리를 타고 쭉쭉 올라가면 그야말로 1만개를 쭉쭉 올라갈 수도 있는 상황이되어버림.
• 그리고, 나의 경우, 한 사람의 sell을 총합 하여 dfs를 하였는데
  • 다른 사람들의 경우 seller의 항목 하나하나부터 dfs를 하였다 → 근데 이렇게 해야 답이 나오더라... !

import java.util.*;
class Solution {
    public Map<String,String> parentMap = new HashMap<>();
    public Map<String,Integer> tot = new HashMap<>(); // 결과 금액
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = {};
        int cur = 0 , rest = 0;
        String parent = null,child = null;
        // set child - parent Map
        for(int i = 0; i< enroll.length;i++){
            parentMap.put(enroll[i],referral[i]);
        // getOrDefault를 하지 않기 위해 먼저 0으로 세팅
            tot.put(enroll[i],0);

        }
        
        // seller 을 돌면서 dfs 식으로 쭉쭉 올라간다
        for(int i =0; i < seller.length; i++){
            cur = 100 * amount[i]; // 이만큼 판매함
            // System.out.println("현재 판매 가격 "+ cur);
            child = seller[i];
            // 이제 쭉쭉 타고 올라가야함
            while(!child.equals("-")){
                rest = cur/10;
                tot.put(child,tot.get(child) + cur-rest);
                cur = rest;
                child = parentMap.get(child);
                if(cur < 1) break;
            }
        }
        // 정답 세팅
        answer = new int[enroll.length];
        for(int i=0;i<enroll.length;i++){
            answer[i] = tot.get(enroll[i]);
            // System.out.println(answer[i]);
        }
        return answer;
    }

}

1보다 작은지 확인하는것보다
0과 같은지 확인하는게 훨씬 효율적일듯하다