[Programmers] 혼자 놀기의 달인 Lv2 (Java)

1. 문제 요약 및 풀이

 

• 구조 파악: 임의의 상자에서 시작하여 카드에 적힌 번호를 따라가며, 이미 열린 상자를 만날 때까지 반복하면
  하나의 그룹(사이클)이 형성된다. 모든 상자는 여러 개의 고정된 그룹으로 나뉜다.
• 점수 계산: 1번 그룹의 크기 * 2번 그룹의 크기
• 목표: 이 게임에서 얻을 수 있는 최고 점수를 구해야 한다. (모든 그룹 중 가장 큰 두 그룹의 크기를 곱한 값)

 

정답 코드

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(int[] cards) {
        int N = cards.length;
        boolean[] opened = new boolean[N];
        ArrayList<Integer> groupSizes = new ArrayList<>();
        
        // 1. 모든 상자를 순회하며 그룹(사이클)의 크기를 찾아서 저장
        for (int i = 0; i < N; i++) {
            if (!opened[i]) { 
                int currentBox = i;
                int currentGroupSize = 0;
                
                while (!opened[currentBox]) {
                    // 현재 상자를 열었다고 표시하고 크기 증가
                    opened[currentBox] = true; 
                    currentGroupSize++;
                    
                    // 다음 상자 인덱스로 이동
                    currentBox = cards[currentBox] - 1; 
                }
                groupSizes.add(currentGroupSize);
            }
        }
        
        // 2. 최고 점수 계산
        
        // 그룹이 2개 미만이면 0점
        if (groupSizes.size() < 2) {
            return 0;
        }
        
        // 크기를 내림차순으로 정렬하여 가장 큰 두 그룹을 선택
        Collections.sort(groupSizes, Collections.reverseOrder());
        
        // 가장 큰 그룹의 크기 * 두 번째로 큰 그룹의 크기
        return groupSizes.get(0) * groupSizes.get(1);
    }
}

 

---

2. 초기 풀이의 논리적 오류

 

문제를 풀 때 "최고 점수" 조건을 간과하고, 점수 계산을 단순화하여 체점 중 실패 케이스 발생

import java.util.ArrayList;

class Solution {
    public int solution(int[] cards) {
        int N = cards.length;
        boolean[] opened = new boolean[N];
        ArrayList<Integer> groupSizes = new ArrayList<>();
        
        // 1. 모든 상자를 순회하며 그룹(사이클)의 크기를 찾아서 저장
        for (int i = 0; i < N; i++) {
            if (!opened[i]) { 
                int currentBox = i;
                int currentGroupSize = 0;
                
                while (!opened[currentBox]) {
                    // 현재 상자를 열었다고 표시하고 크기 증가
                    opened[currentBox] = true; 
                    currentGroupSize++;
                    
                    // 다음 상자 인덱스로 이동
                    currentBox = cards[currentBox] - 1; 
                }
                groupSizes.add(currentGroupSize);
            }
        }
        
        // 2. 점수 계산: (잘못된 로직) 모든 그룹 크기를 곱함
        
        // 그룹이 2개 미만이면 0점
        if (groupSizes.size() < 2) {
            return 0;
        }
        
        int a = 1;
        for(int size:groupSize){
        	a *= size;
        }
        return a;
    }
}