LEVEL 3 : 다단계 칫솔 판매

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

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

 

• 문제

  • 

    문제1

  • 

    문제 2

  • 

    문제 3

  • 

    문제 4

  • 

    문제 5

  • 

    문제 6

  • 

    문제 7

  • 

    문제 8

  • 

    제한사항

---

풀이

• 부모노드를 찾아가는 dfs 문제이다.
• 비용을 담을 배열(정답), 부모 노드를 담을 배열을 선언한다.
  • 모든 노드를 탐색하며, 부모노드의 인덱스를 넣어준다.
  • find함수
  • 만약 부모노드가 없다면 referral[i] == "-" 일 경우, -1 값을 넣어준다.
• 판매된 제품을 반복문을 돌며, 현재 판 제품을 Index와 money값을 가지고 온다
  • dfs(현재 제품을 Index, 가지고 있는 돈, 비용을 담을 배열)
    • 만약 index 가 -1 일경우 center일 경우이므로 멈춘다.
    • 아닐 경우, 현재 index의 배열 위치에 가지고 있는 돈에서 90% 를 저장하고, 10%를 다시 재귀함수를 호출하는데 사용한다.

• public static int[] parents;
  public static int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
  	int[] answer = new int[enroll.length];//정답 배열
      parents = new int[enroll.length]; // 부모의 index를 넣을 배열
      for(int i=0;i<enroll.length;++i) {//모든 노드 탐색
      	parents[i] = find(enroll,referral[i]); // 부모노드의 index를 찾아 넣어준다.
      }
      for(int i=0;i<seller.length;++i) {//판매금액을 돈다
      	String now = seller[i];//현재 판매한 사람
          int money = 100 * amount[i];//현재 판매하여 번 금액
          for(int j=0;j<enroll.length;++j) {//현재 판매한 사람이 몇번째 인덱스 인지 찾는다
          	if(enroll[j].equals(now)) {
      			dfs(j,money,answer); // 찾았다
      			break;
      		}
      	}
      }
      return answer;
      }
  	private static int find(String[] enroll, String parent) {
  		for(int i=0;i<enroll.length;++i) {
  			if(enroll[i].equals(parent)) { // 부모노드가 존재할 경우 "-" 가 아닐 경우
  				return i;//부모노드 인덱스 반환
  			}
  		}
  		return -1;//부모가 center일 경우 -1리턴
  	}
  	private static void dfs( int now, int money, int[] answer) {
  		if(now == -1) { // 내가 center 인경우
  			return;//리턴
  		}
  		answer[now] += money - (money/10); // 현재 값에 90%를 저장한다
  		dfs( parents[now], money/10, answer);//10%로 재귀함수 호출
  		
  	}