[ 알고리즘 ] 코딩 - Programmers - 다단계 칫솔 판매

---

문제 링크

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

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

---

문제 개요

프로그래머스 - Level 3 - (자바) 다단계 칫솔 판매 - HashMap

다단계 예시

파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

판매가 모두 완료된 경우 누적 판매 금액

제한사항

• enroll의 길이는 1 이상 10,000 이하입니다.
  • enroll에 민호의 이름은 없습니다. 따라서 enroll의 길이는 민호를 제외한 조직 구성원의 총 수입니다.
• referral의 길이는 enroll의 길이와 같습니다.
  • referral 내에서 i 번째에 있는 이름은 배열 enroll 내에서 i 번째에 있는 판매원을 조직에 참여시킨 사람의 이름입니다.
  • 어느 누구의 추천도 없이 조직에 참여한 사람에 대해서는 referral 배열 내에 추천인의 이름이 기입되지 않고 “-“ 가 기입됩니다. 위 예제에서는 john 과 mary 가 이러한 예에 해당합니다.
  • enroll 에 등장하는 이름은 조직에 참여한 순서에 따릅니다.
  • 즉, 어느 판매원의 이름이 enroll 의 i 번째에 등장한다면, 이 판매원을 조직에 참여시킨 사람의 이름, 즉 referral 의 i 번째 원소는 이미 배열 enroll 의 j 번째 (j < i) 에 등장했음이 보장됩니다.
• seller의 길이는 1 이상 100,000 이하입니다.
  • seller 내의 i 번째에 있는 이름은 i 번째 판매 집계 데이터가 어느 판매원에 의한 것인지를 나타냅니다.
  • seller 에는 같은 이름이 중복해서 들어있을 수 있습니다.
• amount의 길이는 seller의 길이와 같습니다.
  • amount 내의 i 번째에 있는 수는 i 번째 판매 집계 데이터의 판매량을 나타냅니다.
  • 판매량의 범위, 즉 amount 의 원소들의 범위는 1 이상 100 이하인 자연수입니다.
• 칫솔 한 개를 판매하여 얻어지는 이익은 100 원으로 정해져 있습니다.
• 모든 조직 구성원들의 이름은 10 글자 이내의 영문 알파벳 소문자들로만 이루어져 있습니다.

---

로직

HashMap 2개로 해결했다. 

1. 등록된 판매원과 추천인 사이의 연결 정보를 관리 할 HashMap connect

2. 판매 금액과 판매인 정보를 관리할 HashMap getTotalSell

 

Step 01. 모든 판매원과 추천인 사이의 정보를 저장한다.

Step 02. 판매에 성공한 판매원의 판매금액의 90%를 저장한다. 나머지 10%는 자신을 추천한 사람에게로 넘긴다. 이때 int형으로 90%를 계산하면 금액에 차이가 있으므로 double형으로 변환해서 올림(Math.ceil())을 이용하자.

Step 02 - 1. Step02의 과정을 추천인이 없는 경우(" - ")까지 반복한다.

Step 03. Step 02의 과정을 모든 판매에 성공한 모든 판매원의 수만큼 반복한다.

Step 04. getTotalSell과 enroll의 판매원의 이름을 비교하며 저장된 금액을 출력하면 정답. 이때 getTotalSell에 이름이 없는 경우에는 판매하지 못했으며, 추천인도 없는 경우이므로 0을 넣어준다.

 

---

코드

import java.util.HashMap;
class Solution {
	public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
		HashMap<String, String> connect = new HashMap<String, String>(); // 추천인과 연결된 정보
		HashMap<String, Integer> getTotalSell = new HashMap<String, Integer>(); // 판매 정보
		for (int i = 0; i < enroll.length; i++) { // 모든 추천인과 연결
			String key = enroll[i];
			String value = referral[i];
			connect.put(key, value);
		}

		for (int i = 0; i < seller.length; i++) { // 판매를 한 사람의 수만큼 반복
			String key = seller[i]; // 판매원
			int totalSell = amount[i] * 100; // 판매 금액
			int sell = totalSell * 10 / 100; // 상납 금액
			if (getTotalSell.containsKey(key)) { // 판매원이 이전에 입력된 금액이 있다면 누적
				getTotalSell.put(key, getTotalSell.get(key) + totalSell - sell);
			} else {// 없으면 새로 넣어줌
				getTotalSell.put(key, totalSell - sell);
			}

			String connectPerson = connect.get(key); // 추천인 확인
			while (!connectPerson.equals("-")) { // 추천인이 더이상 없을때까지 반복
            		// 추천인이 현재 누적금액에 있는 경우 더해줌. 금액은 판매 금액의 90%
				if (getTotalSell.containsKey(connectPerson)) { 
					getTotalSell.put(connectPerson,
							getTotalSell.get(connectPerson) + 
                            (int) Math.ceil((double) sell * 90 / 100));
				} else { // 없으면 새로 넣어줌
					getTotalSell.put(connectPerson, (int) Math.ceil((double) sell * 90 / 100));
				}
				sell = sell * 10 / 100; // 다음 추천인의 금액은 현재 판매액의 10%
				connectPerson = connect.get(connectPerson); // 다음 추천인
			}
		}

		int[] answer = new int[enroll.length]; // 모든 사람의 금액 확인
		for (int i = 0; i < enroll.length; i++) {
			String key = enroll[i];
			if (getTotalSell.containsKey(key))
				answer[i] = getTotalSell.get(key);
			else // 판매금액이 없는 경우에는 0원
				answer[i] = 0;
		}
		return answer;
	}
}