[프로그래머스] Lv.2 혼자 놀기의 달인 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/131130

프로그래머스

 

문제 

---

👓 문제 설명

이 문제는 문제를 이해하는 것이 오래 걸리기 때문에 문제 설명을 한 번 하고 들어가겠습니다.

 

1~주어진 숫자 카드의 개수만큼의 카드가 있습니다.

각 각의 카드를 한 장씩 상자에 넣습니다.

 

상자를 무작위로 섞어 일렬로 나열합니다.

상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

 

임의의 상자를 하나 선택해 선택한 상자 안의 숫자 카드를 확인합니다.

다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 확인합니다.

 

숫자에 해당하는 상자를 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

(예를 들어, 현재 7번째 상자를 열었을 때 1번 이 나오는데, 현재 1번 상자는 열려 있기 때문에

1번 상자그룹은 1, 4, 7, 8 상자가 포함됩니다.)

 

이때, 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

 

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려 있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.

 

최종적으로, (1번 상자 그룹에 속한 상자 수)와 (2번 상자 그룹에 속한 상자의 수)를 곱한 값이 게임 점수입니다.

1번 상자 그룹 : 1, 4, 7, 8

2번 상자 그룹 : 2, 5, 6           => 최종 점수 : 4*3 = 12점

---

📖 풀이과정

1. (1번 상자 그룹)에 속할 첫 번째 상자를 1~ n번 상자일 때의 경우를 모두 확인해야합니다.

 

2. i번 상자가 (1번 상자 그룹)에 첫 번째 상자할 때, 이미 열려 있는 상자를 만날 때까지 반복해

(1번 상자 그룹)을 구합니다.

 

3. 모든 상자가 (1번 상자 그룹)에 속하는지 검사하고, 맞다면 0점을 return 아니라면 이후 작업을 수행합니다.

 

 

4. 남은 상자들 중에 임의의 상자를 한 번 더 정하고, 이미 열린 상자를 만날 때 까지 반복해 (2번 상자 그룹)을 구합니다.

 

5. 구한 1, 2번 상자 그룹에 따른 점수를 구하고, 이 점수가 가장 큰 점수인지 확인해 answer에 넣어줍니다.

---

전체 코드

import java.util.*;
class Solution {
    public int solution(int[] cards) {
        int answer = 0;//게임을 해서 얻을 수 있는 최고 점수
        
        for(int i=0;i<cards.length;i++){// i: 1번 상자 그룹의 첫번째로 고른 상자.
            
            //1번 상자 그룹
            Set<Integer> setA = new HashSet<>();
            setA.add(i+1);
            
            int idx=cards[i];
            while(!setA.contains(idx)){
                setA.add(idx);
                idx=cards[idx-1];
            }
            // 1번 상자 그룹을 제외하고 남는 상자가 없으면 -> 0점.
            if(setA.size()==cards.length) return 0;
            
            //2번 상자 그룹
            for(int j=0;j<cards.length;j++){
                if(setA.contains(j+1)) continue;//1번 상자 그룹에 포함된 상자이면 pass
                
                Set<Integer> setB = new HashSet<>();
                setB.add(j+1);
                
                idx=cards[j];
                while(!setB.contains(idx)){
                    setB.add(idx);
                    idx=cards[idx-1];
                }
                //System.out.println("1:"+setA+" "+"2:"+setB);
                
                //게임의 최고점인지 확인.
                if(setA.size()*setB.size()>answer) answer=setA.size()*setB.size();
            }
        }
        
        return answer;
    }
}