[프로그래머스 문제풀이] 다단계 칫솔 판매(with. JAVA)

RyeonD·2021년 11월 12일
0

알고리즘 문제풀이

목록 보기
9/11
post-thumbnail

문제 링크

트리 모양의 구조도를 꺼꾸로 타고 올라가며 계산하는 문제이다.

처음에 마지막 테스트 케이스 10,11,12,13번에서 시간 초과 에러가 났다. 10번 케이스의 경우 파라미터를 추가해줌으로써 해결했지만, 그래도 나머지에서 시간 초과 에러가 났다. 도저히 답이 보이지 않아 다른 사람들이 푼 풀이들을 확인해보았다. 그리고 내 코드의 에러를 발견하였다.

나의 오답

HashMap <String, Integer> map = new HashMap<>();    // 금액 계산을 위한 hashmap

public void calculator(String[] enroll, String[] referral, String sub, int amount) {
    if(amount < 1 && amount > 10000)
        return;
    
    for(int i=0; i<enroll.length; i++) {
        if(enroll[i].equals(sub)) {
            map.put(sub, map.getOrDefault(sub, 0)+(amount-amount/10));
            
            // 추천인(부모)가 없는 경우
            if(referral[i].equals("-")) {
                return;
            }
            
            // 추천인(부모)가 있는 경우
            calculator(enroll, referral, referral[i], amount/10);
            
            return;
        }
    }
}

public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
    int[] answer = new int[enroll.length];
    
    for(int i=0; i<seller.length; i++) {
        calculator(enroll, referral, seller[i], amount[i]*100);
    }
    
    for(int i=0; i<answer.length; i++) {
        if(!map.containsKey(enroll[i])) {
            answer[i] = 0;
            continue;
        }
        
        answer[i] = map.get(enroll[i]);
    }
    
    return answer;
}

내 문제풀이의 오류

  • 사용한 반복문의 개수는 같았다.
  • 다만, 사용한 if문의 개수가 1개 더 많았다.
  • if문이 많을 수 밖에 없는 이유는 seller에 없는 경우가 존재하기 때문이었다.(amount가 0인 판매원이 존재)
  • 따라서 seller를 확인하고, 바로 거꾸로 올라가는 것이 문제였다.
  • enroll을 확인하고, total에 0을 넣어주고, 추천인-판매원 관계를 별도로 저장해줌으로써 해결하였다.

문제 풀이 코드

import java.util.*;

class Solution {
    
    HashMap <String, String> relationship = new HashMap<>();    // 부모-자식 관계 확인을 위한 hashmap
    HashMap <String, Integer> total = new HashMap<>();  // 금액 계산을 위한 hashmap
    
    public void calculator(String sub, int amount) {
        total.put(sub, total.get(sub)+(amount-amount/10));
        
        if(amount == 0 || relationship.get(sub).equals("-")) {
            return;
        }
        
        calculator(relationship.get(sub), amount/10);
    }
    
    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int[] answer = new int[enroll.length];
        
        for(int i=0; i<enroll.length; i++) {
            relationship.put(enroll[i], referral[i]);
            total.put(enroll[i], 0);
        }
        
        for(int i=0; i<seller.length; i++) {
            calculator(seller[i], amount[i]*100);
        }
        
        for(int i=0; i<answer.length; i++) {
            answer[i] = total.get(enroll[i]);
        }
        
        return answer;
    }
}
profile
I'm job hunting. I want to be a sw developer.

0개의 댓글