혼자 놀기의 달인

1차 실행 오류
무작위로 고르는 인덱스에서 하나의 경우의 수 만을 고려함.

import java.util.Vector;

class Solution {
    public int solution(int[] cards) {
        Vector<Integer> selectedIndex = new Vector<Integer>();
        
        int answer = 0;
        int index = 0;
        int count1 = 1;
        int count2 = 1;
        
        boolean fin = false;
        
        // 1번 상자 그룹 개수
        while (true) {
            selectedIndex.add(index); // 선택된 인덱스 저장
            index = cards[index] - 1; // 인덱스를 카드 번호로 저장
            for (int i = 0; i < selectedIndex.size(); i++) {
                if (index == selectedIndex.get(i)) {
                    fin = true;
                    break;
                }
            }
            if (fin) {
                break;
            }
            count1++;
        }
        
        if (selectedIndex.size() == cards.length) {
            answer = 0;
            return answer;
        }
        // 지정되지 않은 다음 최소 인덱스 구하기
        index = 0;
        while (true) {
            fin = true;
            for (int i = 0; i < selectedIndex.size(); i++) {
                if (index == selectedIndex.get(i)) {
                    fin = false;
                    index++;
                    break;
                }
            }
            if (fin) {
                break;
            }
        }
        fin = false;
        // 2번 상자 그룹 개수
        while (true) {
            selectedIndex.add(index); // 선택된 인덱스 저장
            index = cards[index] - 1; // 인덱스를 카드 번호로 저장
            for (int i = 0; i < selectedIndex.size(); i++) {
                if (index == selectedIndex.get(i)) {
                    fin = true;
                    break;
                }
            }
            if (fin) {
                break;
            }
            count2++;
        }
        answer = count1 * count2;
        return answer;
    }
}

2차 실행 오류
원인을 찾을 수 없어 코파일럿을 돌려본 결과 2번째 상자의 개수를 구할 때 index 변수가 재사용되어 모든 경우의 수를 탐색하지 못함.

import java.util.Vector;

class Solution {
    public int solution(int[] cards) {
        Vector<Integer> answers = new Vector<Integer>();
        Vector<Integer> selectedIndex = new Vector<Integer>();
        Vector<Integer> selectedIndex2 = new Vector<Integer>();
        
        int answer = 0;
        int index = 0;
        int count1 = 1;
        int count2 = 1;
        
        boolean fin = false;
        
        for (index = 0; index < cards.length; index++) {
            count1 = 1;
            fin = false;
            selectedIndex.clear();
            // 1번 상자 그룹 개수
            while (true) {
                selectedIndex.add(index); // 선택된 인덱스 저장
                index = cards[index] - 1; // 인덱스를 카드 번호로 저장
                for (int i = 0; i < selectedIndex.size(); i++) {
                    if (index == selectedIndex.get(i)) {
                        fin = true;
                        break;
                    }
                }
                if (fin) {
                    break;
                }
                count1++;
            }
            // 1번 상자 그룹 개수 끝
            
            // 1번 상자에서 모두 가져갔다면 곱은 0
            if (selectedIndex.size() == cards.length) {
                answers.add(0);
                continue;
            }
            // 2번 상자 그룹 개수
            for (index = 0; index < cards.length; index++) {
                count2 = 1;
                fin = true;
                selectedIndex2.clear();
                selectedIndex2.addAll(selectedIndex);
                
                for (int j = 0; j < selectedIndex.size(); j++) {
                    if (index == selectedIndex.get(j)) {
                        fin = false;
                        break;
                    }
                }
                // 앞에서 선택되지 않은 인덱스라면 선택
                if (fin) {
                    fin = false;
                    while (true) {
                        selectedIndex2.add(index); // 선택된 인덱스 저장
                        index = cards[index] - 1; // 인덱스를 카드 번호로 저장
                        for (int i = 0; i < selectedIndex2.size(); i++) {
                            if (index == selectedIndex2.get(i)) {
                                fin = true;
                                break;
                            }
                        }
                        if (fin) {
                            break;
                        }
                        count2++;
                    }
                    answers.add(count1 * count2);
                }
            }
        }
        
        // 최고 점수 구하기
        answer = answers.get(0);
        for (int i = 1; i < answers.size(); i++) {
            if (answer < answers.get(i)) {
                answer = answers.get(i);
            }
        }
        return answer;
    }
}

변수를 재사용 할 때 주의할 것.
위의 문제와 마찬가지로 수학적인 규칙을 찾는 연습이 필요함.

소요 시간: 1시간 43분 15초

import java.util.Vector;

class Solution {
    public int solution(int[] cards) {
        Vector<Integer> answers = new Vector<Integer>();
        Vector<Integer> selectedIndex = new Vector<Integer>();
        Vector<Integer> selectedIndex2 = new Vector<Integer>();
        
        int answer = 0;
        int index = 0;
        int count1 = 1;
        int count2 = 1;
        
        boolean fin = false;
        
        for (index = 0; index < cards.length; index++) {
            count1 = 1;
            fin = false;
            selectedIndex.clear();
            // 1번 상자 그룹 개수
            while (true) {
                selectedIndex.add(index); // 선택된 인덱스 저장
                index = cards[index] - 1; // 인덱스를 카드 번호로 저장
                for (int i = 0; i < selectedIndex.size(); i++) {
                    if (index == selectedIndex.get(i)) {
                        fin = true;
                        break;
                    }
                }
                if (fin) {
                    break;
                }
                count1++;
            }
            // 1번 상자 그룹 개수 끝
            
            // 1번 상자에서 모두 가져갔다면 곱은 0
            if (selectedIndex.size() == cards.length) {
                answers.add(0);
                continue;
            }
            // 2번 상자 그룹 개수
            for (int index2 = 0; index2 < cards.length; index2++) {
                count2 = 1;
                fin = true;
                selectedIndex2.clear();
                selectedIndex2.addAll(selectedIndex);
                
                for (int j = 0; j < selectedIndex.size(); j++) {
                    if (index2 == selectedIndex.get(j)) {
                        fin = false;
                        break;
                    }
                }
                // 1번 상자에 속하지 않는 인덱스라면 선택
                if (fin) {
                    fin = false;
                    while (true) {
                        selectedIndex2.add(index2); // 선택된 인덱스 저장
                        index2 = cards[index2] - 1; // 인덱스를 카드 번호로 저장
                        for (int i = 0; i < selectedIndex2.size(); i++) {
                            if (index2 == selectedIndex2.get(i)) {
                                fin = true;
                                break;
                            }
                        }
                        if (fin) {
                            break;
                        }
                        count2++;
                    }
                    answers.add(count1 * count2);
                }
            }
        }
        
        // 최고 점수 구하기
        answer = answers.get(0);
        for (int i = 1; i < answers.size(); i++) {
            if (answer < answers.get(i)) {
                answer = answers.get(i);
            }
        }
        return answer;
    }
}

정답 코드

import java.util.*;

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

        for (int i = 0; i < n; i++) {
            int now = i;
            int cnt = 0;
            while (!visited[now]) {
                cnt++;
                visited[now] = true;
                now = cards[now] - 1;
            }
            groups.add(cnt);
        }
        Collections.sort(groups, Comparator.reverseOrder());
        return (groups.size() == 1) ? 0 : groups.get(0) * groups.get(1);
    }
}