[알고리즘] 프로그래머스 - 혼자놀기의달인 Lv2 JAVA

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

프로그래머스

package Programmers;

import java.util.*;

public class 혼자놀기의달인 {
    public static void main(String[] args){
        혼자놀기의달인 T = new 혼자놀기의달인();
        int[] cards = {8,6,3,7,2,5,1,4};
        T.solution(cards);
    }
    public int solution(int[] cards) {
        int answer = 0;
        List<ArrayList<Integer>> boxG = new ArrayList<>();
        for (int i = 0; i < cards.length; i++) {
            int sel = cards[i];
            ArrayList<Integer> box = new ArrayList<>();
            while (true){
                sel = cards[sel-1];
                if(!box.contains(sel)){
                    box.add(sel);
                }else {
                    break;
                }
            }
            //box 소그룹 정렬
            box.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
            boxG.add(box);
        }
        //box 대그룹 정렬
        boxG.sort(new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                return o1.size() - o2.size();
            }
        });
        //박스대그룹의 숫자가 1이면 0 return
        if(boxG.size() == 1){
            return 0;
        }
        //대그룹의박스들중 사이즈가 가장큰 배열의 첫번째값
        int maxI = boxG.get(boxG.size()-1).get(0);
        for (int i = boxG.size()-1; i >= 0; i--) {
            List<Integer> tempArr = boxG.get(i);
            int tempI = tempArr.get(0);
            //큰사이즈부터 돌면서 첫번째 인덱스를 비교한다.
            if(tempI != maxI){
                answer = boxG.get(boxG.size()-1).size() * tempArr.size();
                return answer;
            }
        }
        return answer;
    }
}

1. 문제 

  1.1 ) 지문을 구질구질하게 길게 써놨는데 요약하면 이렇다. 

int[] cards = {8,6,3,7,2,5,1,4};

1번째 박스

8(1) -> 4(8) -> 7(4) -> 1(7) -> 8(1) 이미 8번이 있으므로 제외

최종적으로 [ 8, 4, 7, 1 ] 카드를 뽑는거다. 크기는 4

 

2번째 박스 

 index = 1 ~ 6 까지 돌면서 1번째 뽑은 박스숫자와 안겹치면 된다. 

6(2) -> 5(6) -> 2(5) -> 6(2) 이미 6번이 있으므로 제외

최종적으로 [ 6, 5, 2 ] 카드를 뽑고 크기는 3 

 

2번째 박스에 7(4) 를 먼저 뽑아보자

7(4) -> 1(7) -> 8(1) -> 4(8) -> 7(4) 이미 7번이 있으므로 제외

최종적으로 [ 7, 1, 8, 4 ] 이므로 1번째 박스의 내용물이랑 겹친다. 

 

이렇게 쭈욱 2번째 박스를 첫번째 박스하고 안겹치고 사이즈가 가장큰수랑 곱하면 최종점수다. 

 

2. 풀이 

 2.1. for문을 돌면서 cards 를 모두 첫번째로 다 뽑아본다.

 2.2 box에다가 조합수를 담는다. 

   - while 을 돌면서 sel 변수에 따라 포인터가 변하고 box에 이미 숫자가 존재하면 while 문을 빠져나간다.

 2.3 box의 소그룹을 오름차순으로 정렬 ex) 7, 1, 8, 4 -> 1, 4, 7, 8 

 2.4 box의 대그룹 boxG를 크기순으로 정렬한다. (사이즈를 맨뒤부터 비교해서 시간줄이기 위해)

 2.5 boxG의 맨 마지막 인덱스에는 사이즈가 가장큰수의 배열이 들어있을것이고 여기 배열의 첫번째 인덱스를 maxI에다가 넣는다.

 2.6 boxG 의 맨뒤를 제외하고 점차 index 크기를 줄여가며 각 배열의 첫번째 인덱스와 maxI를 비교

 2.7 두개가 다르면 크기를 곱해서 답을 구한다.

 

사이즈가 같고 첫번째 배열의 숫자가 같으면 결국 중복 배열이기때문에 이를 활용함.