프로그래머스 Lv2 혼자 놀기의 달인 문제

• 프로래머스 Lv2 혼자 놀기의 달인 문제
  • 해당 문제의 난이도 상승 원인
    • 박스가 위치한 번호와 안의 내용 번호의 매칭이 필요하다는 점
    • 1번 그룹의 박스를 고른 후 2번 그룹의 처음 시작 시, 발생하는 경우의 수 관리법이 필요하다는 점
  • 해당 문제를 해결한 방법
    • 박스 위치를 나타내는 배열 변수를 생성하고 이를 이용해 위치와 내부 값을 추적
    • 임의의 박스를 선택하기 때문에 처음 -> 마지막까지 선형 순환하는 방식을 선택하고 그에 따라 발생하는 경우의 수를 처리하는 내부 순환문을 작성
    • 1번 그룹에서 나온 박스 수와 2번 그룹에서 나온 박스 수의 곱한 값을 이전에 구했던 최대값과 비교해 나가면서 최종 Max 값을 찾음
  • 문제의 핵심
    • 박스 번호와 내부 번호를 매칭시키는 방법 찾기
    • 1번/2번 그룹의 박스의 곱한 값의 최대값을 구하는 방법 찾기

import java.util.ArrayList;
import java.util.List;

public class Lv2SoloPlay {
    public static void main(String[] args){
        int[] cards = {8,6,3,7,2,5,1,4};
        System.out.print(solution(cards));
    }

    public static int solution(int[] cards) {
        int LEN = cards.length;
        int seatNum = 1;
        int[] seat = new int[LEN + 1];
        for(int i = 0; i < LEN; i++) seat[seatNum++] = cards[i];

        int sum = 0;
        for(int i = 1; i < LEN + 1; i++){
            boolean[] marking = new boolean[LEN + 1];
            int mainSum = 0;

            for(int j = seat[i]; !marking[j]; j = seat[j]){
                mainSum += 1;
                marking[j] = true;
            }

            List<Integer> remain = new ArrayList<>();

            for(int j = 1; j < LEN + 1; j++){
                if(!marking[j]) remain.add(j);
            }
            boolean[] preservArr = marking.clone();

            for(int val : remain){
                int subSum = 0;
                marking = preservArr.clone();
                for(int j = seat[val]; !marking[j]; j = seat[j]){
                    subSum += 1;
                    marking[j] = true;
                }

                sum = Math.max(sum, mainSum * subSum);
            }
        }

        return sum;
    }
}