99클럽 코테 스터디 9일차 TIL (챌린저): [프로그래머스][Java] 다단계 칫솔 판매 - level3

 

문제 보기

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

프로그래머스

 

 

풀이

맨 처음엔 그래프 관계니까 그냥 BFS 방식으로 풀까? 했는데 시간 초과가 났다.

다시 생각해 보니 부모는 꼭 한 명이므로 굳이 그래프 탐색을 사용할 필요가 없다.

부모노드가 없거나, 매출의 10퍼센트가 1원 미만으로 떨어졌을 때 반복문을 종료하면 될 뿐이다.

 

1. 해쉬맵 사용

HashMap<String, Integer> map = new HashMap<>();
for(int i = 0; i < enroll.length; i++) {
  map.put(enroll[i], i);
}

본격적인 계산에 앞서 나는 이 이름의 enroll에서의 인덱스가 몇 번인지 알아볼 수 있도록 HashMap을 만들었다.

이후 seller에서 이름으로 인덱스 번호를 가져오기 위함이다.

 

2. 매출 계산

int[] answer = new int[enroll.length];
for(int i = 0; i < seller.length; i++) {
  int index = map.get(seller[i]);
  int profit = amount[i] * 100;
  while(true) {
    int tip = (int) (profit * 0.1);
    answer[index] += profit - tip;
    profit = tip;
    if(profit < 1) {
      break;
    }
    if(referral[index].equals("-")) {
      break;
    }
    index = map.get(referral[index]);
  }
}

매출을 계산하는 부분이다.

while문을 사용하였고 먼저 금액의 10%가 얼마일지 계산하였다.

여기서 1 미만일 경우 int로 형변환 하는 과정에서 자동으로 0이 될 것이다.

나머지 부분은 정답 배열에서 해당 이름인덱스에 누적시켰다.

 

다음으로 가져갈 매출액이 1 미만이거나 부모노드가 없을 경우 반복문을 빠져나온다.

그리고 referral 배열을 참조해 부모 노드를 가져온다.

 

 

전체 코드

import java.util.HashMap;

class Solution {
  public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
    HashMap<String, Integer> map = new HashMap<>();
    for(int i = 0; i < enroll.length; i++) {
      map.put(enroll[i], i);
    }

    int[] answer = new int[enroll.length];
    for(int i = 0; i < seller.length; i++) {
      int index = map.get(seller[i]);
      int profit = amount[i] * 100;
      while(true) {
        int tip = (int) (profit * 0.1);
        answer[index] += profit - tip;
        profit = tip;
        if(profit < 1) {
          break;
        }
        if(referral[index].equals("-")) {
          break;
        }
        index = map.get(referral[index]);
      }
    }

    return answer;
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/3/77486.%E2%80%85%EB%8B%A4%EB%8B%A8%EA%B3%84%E2%80%85%EC%B9%AB%EC%86%94%E2%80%85%ED%8C%90%EB%A7%A4

CodingTest_AutoSave/프로그래머스/3/77486. 다단계 칫솔 판매 at main · MetroDefro/CodingTest_AutoSave