🦾 오늘의 컨디션 및 특이사항(개인 일정 등)

• 수면 시간
  • 6시간
• 학습 시간
  • 11 : 00 ~ 14 : 30
  • 23 : 00 ~ 00 : 00
• 특이사항

---

📑 세부 학습 내용

📅 스케쥴

• 3시간 독서 + 궁금한 개념 조사 및 학습 + 1시간 30분 코딩테스트 및 풀이 리뷰
• 총 4시간 30분
  
  

📖 도서 정독 및 실습

실전 레디스 : 기초, 실전, 고급 단계별로 배우는 레디스 핵심 가이드

• 캐싱 등 RDB 의 보조 역할을 해줄 NoSQL 중 가장 범용적이고 유지보수가 잘 진행 중인 Redis 의 구조부터 기초, 심화 내용, 사용법 등을 확실하게 이해하여, 이후의 프로그래밍에 있어 자신 있고 근거 있게 레디스를 채택하고 사용할 수 있는 개발자를 목표로 독서 시작
• 2.5.3 Set형 실행 예시 (p.113) ~ 2.6.2 Sorted Set형 주요 명령어 (p.123, 진행 중)
  
• 도서 내 모든 내용 이해 및 실습 완료
  • 궁금한 부분은 따로 조사 후 학습
    
    

✏️ 코딩 테스트

• 1 SOLVE 및 깃허브 커밋
• 프로그래머스 - 77486
  • https://school.programmers.co.kr/learn/courses/30/lessons/77486
• 문제 유형 : 트리 탐색 , 시뮬레이션/구현
• https://github.com/oneplast/ProgrammersCT/commit/bdc5f59afc5f6f755610586a2b1f4f58805af5a7

🔨 트러블 슈팅

• 최초 풀이

class Solution {

    Map<String, Employee> empMap = new HashMap<>();

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int size = enroll.length;

        empMap.put("-", new Employee("-", ""));
        for (int i = 0; i < size; i++) {
            Employee emp = new Employee(enroll[i], referral[i]);
            empMap.put(enroll[i], emp);
        }

        for (int i = 0; i < seller.length; i++) {
            int earning = amount[i] * 100;
            Employee sellerEmp = empMap.get(seller[i]);
            while (true) {
                if (!sellerEmp.superName.isEmpty()) {
                    int benefit = earning - (earning / 10);
                    earning /=  10;
                    sellerEmp.addBenefit(benefit);
                    sellerEmp = empMap.get(sellerEmp.superName);
                } else {
                    sellerEmp.addBenefit(earning);
                    break;
                }
            }
        }

        return Arrays.stream(enroll)
                .mapToInt(name -> empMap.get(name).benefit)
                .toArray();
    }

    class Employee {
        String name;
        String superName;
        int benefit;

        public Employee(String name, String superName) {
            this.name = name;
            this.superName = superName;
            benefit = 0;
        }

        public void addBenefit(int benefit) {
            this.benefit += benefit;
        }
    }
}

• 트리 탐색을 이용한 풀이
• 시간 복잡도 O(N * M)
  • 1 <= N <= 10,000 , 1 <= M <= 100,000
    • M 은 사실상 트리의 depth 이므로, 웬만해서 최악의 경우까지 도달하지 않음
      • ex) 100,000
  • seller 조회 - O(N)
    • 내부에서 empMap 의 Employee 조회 : 최악의 경우 O(M)
  • 총 O(N * M) 의 시간복잡도 소요
    
    

🤔 문제점

• 해시맵을 조회하는 과정에서, 객체 조회 시 equalsAndHashCode 등 생각보다 많은 오버헤드 연산으로 인하여 일부 테스트케이스에서 시간 초과가 발생

• 최종 풀이

class Solution {

    Map<String, Integer> empMap = new HashMap<>();

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        int size = enroll.length;
        int[] parent = new int[size];
        int[] benefits = new int[size];

        for (int i = 0; i < size; i++) {
            empMap.put(enroll[i], i);
        }

        for (int i = 0; i < size; i++) {
            if (referral[i].equals("-")) {
                parent[i] = -1;
            } else {
                parent[i] = empMap.get(referral[i]);
            }
        }

        for (int i = 0; i < seller.length; i++) {
            int curIdx = empMap.get(seller[i]);
            int earning = amount[i] * 100;

            while (curIdx != -1) {
                int benefit = earning / 10;
                benefits[curIdx] += earning - benefit;
                earning = benefit;
                curIdx = parent[curIdx];
            }
        }

        return benefits;
    }
}

• 기존 해시맵 객체 조회를 단순 Integer 인덱스 조회로 변경
  • 기존 Employee 와의 연결을 부모 인덱스 조회 방식으로 변경
• 시간 복잡도 O(N * M)
  • 기존과 동일하지만, 내부적으로 기존보다 훨씬 빠른 연산 수행
  • 총 O(N * M) 의 시간복잡도 소요

---

💡 어려웠던 것 || 알게 된 것

• 금일은 없음