[프로그래머스] Lv.3 다단계 칫솔 판매 JAVA 풀이

문제 Lv.3 다단계 칫솔 판매 

 :  하위 직원이 칫솔 판매하면 10프로는 상사한테 넘긴다 (계속 반복하면서 center까지도 수익금 10% 전달)

 :   단 더이상 10%로 나눠지지 않는다면 되는 단계까지만 한다

 

 

 - [enroll] : 모든 판매원의 이름을 담고 있는 배열

 - [referral] : enroll배열과 연결된 직속 상사 
                      "-" 표시가 있다면 제일 높은 상사

 - [seller] : 판매한 직원

 - [amount] : 판매한 칫솔 개수 (seller와 연결지어 보면 된다)

 

 

예시)

 

enroll	referral	income
john	-	360
mary	-	958
edward	mary	108
sam	edward	0
emily	mary	450
jaimie	mary	18
tod	jaimie	180
young	edward	180

 

seller	amount	income
young	12	1200
john	4	400
tod	2	200
emily	5	500
mary	10	1000

 

 

한 과정만 예로 들자면 young 이라는 직원이 칫솔 12개를 팔아서 1200원의 수익을 냈다면?

 

1. 90%인 1080원은 본인이 갖는다
2. 10%인 120은 직속 상사 edward가 갖는다
3. edward는 120원의 90%인 108원만 남긴다
4. 10%의 12원은 직속 상사인 mary가 갖는다
5. mary는 12원의 90%인 1원만 남긴다
6. 남은 10% 1원은 center가 가져간다

 

 

[설명]

 

배열은 다르나 순서가 서로서로 연결된 개념들이 많아서 Map 사용
한 뿌리씩 깊게 파고 든다는 점에서 DFS 사용

<Map>

:  키(Key)와 값(Value) 두 쌍으로 데이터를 보관하는 자료구조

   (리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 key를 통해 value값을 구한다)
:  키는 맵에 오직 유일하다(같은 맵에 중복 X)

   값(value)은 중복돼도 OK

 

<HashMap>

 

:  해싱된 맵

:  비슷하게는 Hashtable이 있다

   두 개의 차이점  -  Thread 관점에서의 안전한 것은 Hashtable

                            -  안전하지는 않지만 속도가 빠른 HashMap

  1) 맵 선언

  :  Map<타입, 타입> 변수명 = new HashMap<>();

     (ex) Map<String,Integer> m = new HashMap<>();

 

  :  앞에는 Map, 뒤에는 HashMap 을 쓴 이유는 Map이 인터 페이스이기 때문이다

     (인터페이스는 선언만 가능, 객체 생성은 불가능)

      때문에 자식인 HashMap으로 객체를 생성한다

     (HashMap은 부모인 Map의 메소드들을 강제 상속받음)

 

  2) 맵에 데이터 저장

  :  변수명.put("Key", "Value");

     (ex) m.put("홍길동", "1")

     * 이때 만약 같은 키에 다른 값을 또 저장한다면 맨 마지막 데이터가 덮어쓴다

 

 3) 맵 안의 값 가져오기

 :  변수명.get(key);

 

  4) 데이터 수정

  :  변수명.put("Key", "Value"); 덮어씌기

  :  변수명.replace("Key", "Value"); 수정하기

 

 

[코드]

import java.util.*;
class Solution {
    static Map<String,Integer> map = new HashMap();
    static Map<String,String> recommand = new HashMap();
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] count = new int[enroll.length];
        
        for(int i =0; i<enroll.length;i++){
            map.put(enroll[i],0);
            recommand.put(enroll[i],referral[i]);
        }
        
        for(int i=0; i<seller.length; i++){
            dfs(seller[i],amount[i]*100);
        }
        
        for(int i=0; i<enroll.length;i++){
            count[i] = map.get(enroll[i]);
        }
        
        return count;

    }
    
    public static void dfs(String name, int income){
        if(name.equals("-") || income==0){
            return;
        }
        
        int parents = income/10; 
        int mine =   income-parents;
        String next = recommand.get(name);
        map.replace(name,map.get(name)+mine);
        dfs(next,parents);
    }
}

 

 :  static Map<String,Integer> map = new HashMap(); 맵 선언 (모든 직원이름, 가진 금액)
    static Map<String,String> recommand = new HashMap();  맵 선언 (모든 직원이름, 연결된 상사)
   
 :  int[] count = new int[enroll.length];  최종적으로 출력할 값 (모든 직원의 가진 금액)
        
 :  for(int i =0; i<enroll.length;i++){  모든 직원이름
            map.put(enroll[i],0);  key 직원이름, value 가진 돈 → 직원이름 대면 돈 얼마인지 알 수 있 다
            recommand.put(enroll[i],referral[i]);  key 직원이름, 직속 상사 → 직원이름 대면 직속 상사 알 수 O
    }
        
    for(int i=0; i<seller.length; i++){  판매된 경우의 수만 볼 것
            dfs(seller[i],amount[i]*100);  판매한 사람 이름, 판매한 개수*100 (= 소득)을 dfs에 대입
    }
        
 :  for(int i=0; i<enroll.length;i++){  직원 수 만큼 돌기
            count[i] = map.get(enroll[i]);  맵에 저장된 직원이름(= key)의 value 데이터(= 금액)를 가져오는 것
              
    }
        
    return count;  최종 금액이 담긴 count 출력 

    
 :  public static void dfs(String name, int income){  dfs 실행
        if(name.equals("-") || income==0){  입력받은 이름에 -가 들어가거나 소득이 0이라면 종료
            return;
        }
        

        int parents = income/10;  상사에게 떼줄 돈
        int mine =   income-parents;  10% 금액 제외한 나머지는 내가 가질 돈   

        String next = recommand.get(name);  recommand 라는 맵에서 입력받은 name(=key)의 value 값
                                                                       recommand 맵의 key = enroll, value = referral

        map.replace(name,map.get(name)+mine);  입력받은 name(=key) 값을 보고 해당 값의 value 수정

                                                                                value는 맵에서 입력받은 직원(=key) 값의 가진 금액과
                                                                                칫솔을 팔아 10% 뗀 나머지 금액을 합친다

        dfs(next,parents);  referral(직속상사)와 parents(상사에게 떼줄 10% 금액)으로 다시 한 번 dfs 반복
    }
}

 

 

[시간 복잡도]

 

• solution
  enroll의 길이 만큼 map 과 recommand 맵이 돌아가고 있다 = O(N)
  seller의 길이 만큼 dfs 메서드를 호출한다 = O(E)
  enroll의 길이 만큼 count가 돌아가고 있다 = O(N)
  
  
• dfs
  그냥 계속해서 호출하거나 찾아가거나 업데이트 하는거라 입력 크기와 무관하다 = O(1)

 

고로 시간 복잡도는 O(N+E) 이고 N은 전체 직원 수, E는 칫솔을 판매한 직원 수가 된다

 

 

 

 

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

프로그래머스

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *