문제
기존 코드 - 시간초과 실패
import java.util.*;
class Solution {
List<Person> personList = new ArrayList<>();
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
// 1. 계층 관계 객체 생성
for (int i = 0; i < enroll.length; i++) {
String name = enroll[i];
String referralName = referral[i];
Person person = new Person();
person.name = name;
if (!referralName.equals("-")) {
person.parentName = referralName;
}
personList.add(person);
}
// 2. 판매 금액 보면서 금액 배분
for (int i = 0; i < seller.length; i++) {
String sellerName = seller[i];
int sellMoney = amount[i] * 100;
Person target = personList
.stream()
// seller[i] 사용 불가 : i가 effective final이 아님
.filter(person -> person.name.equals(sellerName))
.findFirst().get();
// 1~100 개 팔았으니 일단 무조건 90퍼로 먹고들어감
target.money += (int)(sellMoney * 0.9);
// 부모가 있으면 10퍼 넘기기, 만약 없는 녀석들이라면 그냥 본사에 헌납한 것으로 고려 x
if (target.parentName != null) {
tenPercent(target.parentName, (int)(sellMoney * 0.1));
}
}
// 3. 결과 반환
int[] resultArr = new int[enroll.length];
for (int i = 0; i < enroll.length; i++) {
String target = enroll[i];
resultArr[i] = personList.stream()
.filter(p -> p.name.equals(target))
.findFirst().get().money;
}
return resultArr;
}
private void tenPercent(String parentName, int incentive) {
// 1. 부모 찾기
Person parent = personList.stream()
.filter(p -> p.name.equals(parentName))
.findFirst().orElse(null);
// 2. 90% 먹고
int nextParentParent = (int) (incentive * 0.1);
parent.money += incentive;
// 3-1. 부모의 부모에게 다시 대상금 넘길 수 있다면 10% 뺏기
if (nextParentParent > 0) {
parent.money -= nextParentParent;
}
// 3-2. 부모가 있으면서 계속 분배금 분배 가능하면 재귀 호출
if (parent.parentName != null) {
tenPercent(parent.parentName, nextParentParent);
}
}
}
class Person {
String name;
int money;
String parentName;
}개선 코드2 - 재귀 호출 제거 -> 시간초과 실패
import java.util.*;
class Solution {
List<Person> personList = new ArrayList<>();
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
// 1. 계층 관계 객체 생성
for (int i = 0; i < enroll.length; i++) {
String name = enroll[i];
String referralName = referral[i];
Person person = new Person();
person.name = name;
if (!referralName.equals("-")) {
person.parentName = referralName;
}
personList.add(person);
}
// 2. 판매 금액 보면서 금액 배분
for (int i = 0; i < seller.length; i++) {
String sellerName = seller[i];
int sellMoney = amount[i] * 100;
Person target = personList
.stream()
// seller[i] 사용 불가 : i가 effective final이 아님
.filter(person -> person.name.equals(sellerName))
.findFirst().get();
// 1~100 개 팔았으니 일단 무조건 90퍼로 먹고들어감
target.money += (int)(sellMoney * 0.9);
// 부모가 있으면 10퍼 넘기기, 만약 없는 녀석들이라면 그냥 본사에 헌납한 것으로 고려 x
if (target.parentName != null) {
tenPercent(target.parentName, (int)(sellMoney * 0.1));
}
}
// 3. 결과 반환
int[] resultArr = new int[enroll.length];
for (int i = 0; i < enroll.length; i++) {
String target = enroll[i];
resultArr[i] = personList.stream()
.filter(p -> p.name.equals(target))
.findFirst().get().money;
}
return resultArr;
}
private void tenPercent(String parentName, int incentive) {
while (true) {
String target = parentName;
// 1. 부모 찾기
Person parent = personList.stream()
// parentName 사용 불가 : 참조가 계속 변하기에 effective final이 아님
.filter(p -> p.name.equals(target))
.findFirst().orElse(null);
// 2. 90% 먹고
int nextParentParent = (int)(incentive * 0.1);
parent.money += (incentive - nextParentParent);
// 3-1. 만약 1원 미만의 돈을 상위에 넘기는 셈이라면 종료시키기
// 부모가 없으면 -> 자기가 마지막이니 만약 넘길 돈이 있어도 그냥 센터에만 주면되니 그냥 함수 끝
if (nextParentParent == 0 || parent.parentName == null) {
break;
}
// 3-2. 부모가 있으면서 계속 분배금 분배 가능하면 재귀 호출(값 갱신)
parentName = parent.parentName;
incentive = nextParentParent;
}
}
}
class Person {
String name;
int money;
String parentName;
}개선 코드3 - List 대신 Map 도입
import java.util.*;
class Solution {
Map<String, Person> personMap = new HashMap<>();
public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
// 1. 계층 관계 객체 생성
for (int i = 0; i < enroll.length; i++) {
String name = enroll[i];
String referralName = referral[i];
Person person = new Person();
person.name = name;
if (!referralName.equals("-")) {
person.parentName = referralName;
}
personMap.put(name, person);
}
// 2. 판매 금액 보면서 금액 배분
for (int i = 0; i < seller.length; i++) {
String sellerName = seller[i];
int sellMoney = amount[i] * 100;
Person target = personMap.get(sellerName);
// 1~100 개 팔았으니 일단 무조건 90퍼로 먹고들어감
target.money += (int)(sellMoney * 0.9);
// 부모가 있으면 10퍼 넘기기, 만약 없는 녀석들이라면 그냥 본사에 헌납한 것으로 고려 x
if (target.parentName != null) {
tenPercent(target.parentName, (int)(sellMoney * 0.1));
}
}
// 3. 결과 반환
int[] resultArr = new int[enroll.length];
for (int i = 0; i < enroll.length; i++) {
resultArr[i] = personMap.get(enroll[i]).money;
}
return resultArr;
}
private void tenPercent(String parentName, int incentive) {
while (true) {
// 1. 부모 찾기
Person parent = personMap.get(parentName);
// 2. 90% 먹고
int nextParentParent = (int)(incentive * 0.1);
parent.money += (incentive - nextParentParent);
// 3-1. 만약 1원 미만의 돈을 상위에 넘기는 셈이라면 종료시키기
// 부모가 없으면 -> 자기가 마지막이니 만약 넘길 돈이 있어도 그냥 센터에만 주면되니 그냥 함수 끝
if (nextParentParent == 0 || parent.parentName == null) {
break;
}
// 3-2. 부모가 있으면서 계속 분배금 분배 가능하면 재귀 호출(값 갱신)
parentName = parent.parentName;
incentive = nextParentParent;
}
}
}
class Person {
String name;
int money;
String parentName;
}로직 설명
계층 관계 객체 생성하여 저장
- personMap에 Person 객체를 생성하여 저장한다.
- Person Class : 접근 제어자 private 설정 및 getter, setter가 실제 코딩엔 캡슐화원칙 지키는 것이겠지만.. 코드 길이상 그냥 default 접근자로 사용했습니다.
판매 금액 보면서 금액 배분
우선 판매금액 먹기
- seller로 판매자 이름을 다 돌면서 90%의 이익을 일단 줘버립니다.
- 판매금액 * 0.9로 90% 금액을 추출합니다.
- 무조건 1개 이상 팔린 데이터기에 100 * 0.9 = 90원
- 최소 90원은 먹고 들어가고, 단순 90퍼 먹을 때는 소수점 영향을 절대 안받습니다.
- 부모가 있다면 10%를 상위로 넘겨버립니다.
- 부모가 없다는 것은 바로 추천인 없는거라 본사에만 10% 주는 것인데 위 로직에서 10% 금액 날렸기에 고려하지 않습니다.
10% 상위로 보내기
- 부모 객체를 찾아옵니다.
- 해당 부모 객체가 우선 90%를 먹습니다.
- 10%를 구해서 빼준 이유
12 원을 edward 로부터 받은 mary 는 10% 인 1 원을 센터에 (즉, 민호에게) 배분하고 자신은 나머지인 11 원을 가집니다.
- 12원이 넘어왔을 때 90%를 계산 -> 10.8원 -> 소수점 절삭 -> 10원
- 실제로는 11원으로 계산해야 함 -> 10%를 구해서 빼주는 것이 소수점 연산 안전
- 10%를 구해서 빼준 이유
- 반복문 종료
- 다음 부모 찾을 때 부모가 없는 경우 : 본사에 10% 바로 줘야하는데 이미 90%만 먹었기 때문에 본사 준셈으로 치기 때문에 바로 종료합니다.
- 1원 미만인 경우엔 nextParentParent가 0일테니까 기존에 더해준 금액도 신경 안써도 되고 반복 끝내면 됩니다.
- 나머지 10%를 부모로 주기 위해 재귀함수 호출 -> (변경) parentName, incentive 갱신
결과 반환
- 참여자 순으로 반환해야 하니 map에서 가져다가 반환
배운점
- 시간 초과를 해결할 때 재귀 함수를 while문 바꿨더니 실패했던 일부 케이스가 성공한 것에 재귀함수 보다는 반복문 짤 수 있으면 더 낫겠다 싶었다.
- 도저히 복잡도를 줄일 방법을 몰랐는데, stream으로 list를 순회하지 말고 map을 그냥 list처럼 사용하니 복잡도가 줄었다. map을 리스트로서도 그냥 사용할 수도 있구나 싶었던 신기한 경험
- stream에서 filter 사용할 때 람다식 사용에서 예외를 마주쳤다.
- 람다식에 외부 지역변수는 final이나 effective final만 사용 가능하다는 점 학습
- 람다 내부 변수는 상관 없음!!
for (int i = 0; i < seller.length; i++) {
int sellMoney = amount[i] * 100;
Person target = personList
.stream()
// 람다 외부에서 선언한 지역변수 i가 effective final이 아니기 때문에 불가
.filter(person -> person.name.equals(seller[i]))
.findFirst().get();private void tenPercent(String parentName, int incentive) {
List<Person> sample = new ArrayList<>();
while (true) {
String target = parentName;
// 1. 부모 찾기
Person parent = sample.stream()
// parentName의 참조가 계속 변경됨
// effective final이 아니기 때문에 매번 target 지역변수 초기화
.filter(p -> p.name.equals(parentName))
.findFirst().orElse(null);
....
parentName = parent.parentName;
incentive = nextParentParent;
}
}local variables referenced from a lambda expression must be final or effectively finaleffective final
정의
- final 키워드가 선언되지 않은 변수지만 값이 재할당 되지 않아 final과 유사하게 동작
- Java 8부터 도입, 익명 클래스 또는 람다식 사용
- 익명 클래스 또는 람다식에서 참조하려는 외부 지역 변수가 final 혹은 선언 후 참조 변경되지 않는 effective final인 경우만 접근 가능
effective final 간주 조건
- final 선언 x
- 초기화 후 다시 할당 x
- 전위 또는 후위에 증감 연산자 사용 x
- 객체 : 참조 변경 x
effective final은 그래서 왜 필요하지?
- 답은 람다 캡처링!
- 람다에서는 외부에 정의된 변수를 사용할 때 내부에서 사용할 수 있도록 변수 복사본 생성
- 람다는 별도의 스레드에서 실행될 수 있다.
- 그러면 람다가 실행될 시점에 기존에 지역 변수를 선언한 스레드가 죽는다면?
- 람다는 어디서 참조를 하냐말이오!
- 그래서 람다가 별도 스레드에서 동작할 때 해당 스레드에 복사함
- 그러면 인스턴스 변수는 상관없는거 아냐?
- ㅇㅇ 맞긴함 Heap에 저장되니
- 하지만? 멀티스레드 환경에서 실행 순서 예측 불가
- 람다가 동작할 때 어떤 객체를 사용할 지 알 수 없어 불가능
- 따라서 람다에서 외부 참조 변수 사용에도 effective final 필요
람다 내부 선언 변수는 effective final이 아니여도 된다.
- 람다 내부 선언 변수는 어차피 같은 스레드에 선언되어 람다가 종료될 때 같이 사라지니 사용 가능
- 값이 변하던 말든 무관!!!
IntStream.range(0, seller.length).forEach(i -> {
Person target = personList.stream()
// i는 람다 내부에서 선언한 변수라 effective final 아니여도 됨
.filter(person -> person.name.equals(seller[i])) // seller[i]를 사용
.findFirst()
.orElse(null);
});출처
- 개선2, 3 코드 - 뤼튼
- 자바의 effectively final
- (Java) 람다 캡처링과 final 제약조건
비슷한 어려움을 겪는 누군가에게 도움이 되길