📑 세부 학습 내용

📅 스케쥴

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

🧷 학습 시간 인증

📖 도서 정독 및 실습

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

• 캐싱 등 RDB 의 보조 역할을 해줄 NoSQL 중 가장 범용적이고 유지보수가 잘 진행 중인 Redis 의 구조부터 기초, 심화 내용, 사용법 등을 확실하게 이해하여, 이후의 프로그래밍에 있어 자신 있고 근거 있게 레디스를 채택하고 사용할 수 있는 개발자를 목표로 독서 시작
• 5.7 벤치마크 (p.379) ~ 7.5 레플리케이션 도입 방법 (p.481)
• 도서 내 모든 내용 이해 및 실습 완료
  • 궁금한 부분은 따로 조사 후 학습
    
    

✏️ 코딩 테스트

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

🔨 풀이 변경점

• 이전 풀이

class Solution {

    int n;
    int[] dp;
    List<Integer> groups;

    public int solution(int[] cards) {
        n = cards.length;
        dp = new int[n];
        groups = new ArrayList<>();
        Arrays.fill(dp, 1);

        int group = -1;
        int groupIdx = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] < 0) {
                continue;
            }

            dp[i] = group;
            groups.add(1);

            int nextIdx = cards[i] - 1;
            while (dp[nextIdx] != group) {
                dp[nextIdx] = group;
                groups.set(groupIdx, groups.get(groupIdx) + 1);
                int curVal = cards[nextIdx];
                nextIdx = curVal - 1;
            }

            --group;
            ++groupIdx;
        }

        if (group >= -2) {
            return 0;
        }

        groups.sort((a, b) -> b - a);

        return groups.get(0) * groups.get(1);
    }
}

• 코드 자체는 맞으나, 불필요한 연산, 로직 존재

• 새로운 풀이

class Solution {

    int n;
    boolean[] visited;
    List<Integer> groups;

    public int solution(int[] cards) {
        n = cards.length;
        visited = new boolean[n];
        groups = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int groupCnt = 0;
            int value = dfs(cards, i, groupCnt);
            if (value > 0) {
                groups.add(value);
            }
        }

        if (groups.size() < 2) {
            return 0;
        }

        groups.sort(Collections.reverseOrder());

        return groups.get(0) * groups.get(1);
    }

    private int dfs(int[] cards, int idx, int groupCnt) {
        if (visited[idx]) {
            return groupCnt;
        }

        visited[idx] = true;
        int nextIdx = cards[idx] - 1;
        return dfs(cards, nextIdx, groupCnt + 1);
    }
}

• 그룹을 따로 계산할 필요가 없으므로, 기존 int[] dp 대신 boolean[] visited 사용
• DFS 로 visited 계산하고, 개수를 계산하여 0보다 크면 groups 에 추가
• 나머지 알고리즘은 이전과 동일
• 최종 시간복잡도 : O(N * logN)
  • 정렬 시간복잡도 : O(N * logN)
  • 최종 시간복잡도 : O(N * logN)

---

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

• 금일은 없음