문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/77486
2021 Dev-Maching에서 나온 문제
카카오 기출문제만 풀다와서 그런진 모르겠는데, Level 3 치곤 쉽게 풀었다.
만약 카카오 코딩 테스트에서 나왔다면, Level 2 쯤 아니었을까?
문제 핵심 및 풀이
그림에서 보면 알 수 있듯이, 트리 구조가 형성되는 것을 알 수 있다.
그리고 해당 문제에서는 자신을 추천한 사람을 아는 것이 중요한데,
parent [i] = k : i를 추천한 사람이 k이다.
이런 식으로 정의하도록 한다.
사람 이름 문자열을 매핑
여기서 생각해야 할 것은 트리의 각 노드들이 사람이름(문자열)이라는 점이다.
그래서 parent의 인덱스로 문자열을 사용하려면 Map을 사용해야 한다.
parent의 인덱스로 문자열을 사용해도 되지만,
해당 문제에서는 enroll과 referral의 각 인덱스가 의미하는 바가 연관된다.
referral의 각 인덱스는 enroll의 인덱스에 있는 사람이 주체이다.
그러니까 referral [i]는 enroll [i]을 추천한 사람을 의미한다.
그렇기 때문에 enroll에 각 문자열에 있는 사람을 번호로 매핑할 수 있다면,
더 이상의 map은 필요 없고, 정수만 가지고 이를 다룰 수 있을 것이다.
1번 입출력 예를 들면, enroll [0] = "john"이니까
"john" -> 0번으로 매핑한다면, parent [0] = k가 john을 추천한 사람이 k를 의미하게 할 수 있다.
계산 및 전달 방식
두 번째로 고려해야 할 것은 seller와 amount를 통해,
자신이 얻을 가격을 책정하고, 10%를 위로 넘기는 것이다.
위로 넘겨야 할 10%를 구하는 것과,
자신이 얻을 금액을 알아내는 것은 쉽다.
문제는 이제 누구한테 넘겨야 하며,
이를 언제까지 실행해야 하는 것인가인데
넘기는 사람을 알아내는 것은 쉽다.
seller에서 파는 사람의 이름 문자열을 통해
enroll에서의 매핑된 인덱스 번호를 알 수 있다.
parent [해당 번호]를 하면 자신을 호출한 사람을 알 수 있다.
다음으로, 언제까지 실행해야 하냐는 것인데,
문제에서 말했듯이 0원 단위 밑에 소수점 자리는
존재하지 않기 때문에 10%씩 떼다가 0이 되는 시점에서 중단하면 된다.
또한, referral이 "-"인 경우는 자신을 추천한 사람이 없다는 뜻이므로,
이럴 경우에도 위로 넘기는 작업을 중단한다.
계속 10%씩 위로 넘기는 행위는 같은 행위의 반복이기 때문에
재귀함수를 통하면 쉽게 구현할 수 있다.
이는 문제 구현 단계에서 코드로 보는 것이 훨씬 편하다.
실수하기 쉬운 부분
구현하기는 간단한데 값을 위로 넘길 때
예외처리를 제대로 안 해주면 제출했을 때 시간초과가 나는 케이스가 존재할 것이다.
위에서 언급했듯이 재귀함수를 계속 돌리다가 값이 0이 되거나,
그 사람을 추천한 사람이 없을 경우에는 return을 통해 재귀함수를 끝내야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map<string,int> people; // 사람을 인덱스로 매핑
vector<string> parent; // 인덱스를 추천한 사람을 의미하는 변수
vector<int> answer; // 각 인덱스의 최종 결과
// 금액을 계산하고 위로 돈을 넘기는 함수
// receiver : 돈을 받는 사람 , price : 받을 가격
void sends(string receiver, int price){
// 10을 나눈 가격이 0이 되거나, receiver가 없다면 리턴
if(price == 0 || receiver == "") return;
int sending = price / 10; // 10% 뗀 값
int next = people[receiver]; // 해당 사람의 매핑 번호
price -= sending; // 원금 - 10% 뗀 값
answer[next] += price; // 값 추가
sends(parent[next],sending); // 추천한 사람을 주체로 sends 재귀 호출
}
vector<int> solution(vector<string> enroll, vector<string> referral,
vector<string> seller, vector<int> amount) {
parent.assign(enroll.size(),""); // parent의 정의
answer.assign(enroll.size(),0); // 각 인덱스의 돈을 0으로 초기화
for(int i = 0; i < enroll.size(); i++){
people[enroll[i]] = i; // 매핑 작업
if(referral[i] == "-") continue; //
parent[i] = referral[i]; // i의 추천자를 referaal[i] 로 지정
}
// 계산
for(int i = 0; i < seller.size(); i++){
sends(seller[i],amount[i] * 100);
}
return answer;
}↑
Java 구현 코드
↓
import java.util.*;
class Solution {
// 사람을 인덱스로 매핑
public Map<String,Integer> people = new HashMap<>();
public int[] answer; // 각 인덱스의 최종 결과
public String[] parent;// 인덱스를 추천한 사람을 의미하는 변수
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
parent = new String[enroll.length];
answer = new int[enroll.length];
for(int i = 0; i < enroll.length; i++) {
people.put(enroll[i],i); // 매핑 작업
if(referral[i].equals("-")) continue;
parent[i] = referral[i]; // i의 추천자를 referral[i]로 지정
}
// 계산
for(int i = 0; i < seller.length; i++){
sends(seller[i],amount[i] * 100);
}
return answer;
}
// 금액을 계산하고 돈을 위로 넘기는 함수
// seller : 돈을 받는 사람, price : 받을 돈
public void sends(String seller, int price){
// 10을 나눈 가격이 0이 되거나, seller가 없다면 종료
if(price <= 0 || seller == null) return;
int sending = price / 10; // 10% 뗀 돈
price -= sending; // 자신이 받을 돈
answer[people.get(seller)] += price; // 자신에게 돈을 더함
// 자신을 추천한 사람을 주체로하는 sends 호출
sends(parent[people.get(seller)],sending);
}
}↑
시행착오
20분 남짓 남겨두고 풀었던 문제, 시간이 부족해서 못 풀었지 10분만 더 있어도 풀었을 것 같다.
문제 이해하는데 조금 걸렸고, 그다음에는 null exception이 뜨는 것을 캐치하지 못해서 애를 좀 먹었다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me