[JAVA] 프로그래머스 level2 혼자 놀기의 달인

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

프로그래머스

코딩테스트 연습 > 연습문제 > 혼자 놀기의 달인

 

문제 접근

문제에서 제공하는 데이터는 2이상 100 이하의 자연수를 하나 정하고 상자를 무작위로 섞고 번호까지 붙인 상태로 주어진다. 우리는 해당 데이터로 게임을 시뮬레이션해서 최고 점수가 나오는 방법만 찾으면 된다.

 

예시로 주어진 입출력을 분석해 보자  

cards          
[8,6,3,7,2,5,1,4]

result

12

 

(8,6,3,7): 1번 상자

(2,5,4): 2번 상자 

4 * 3 = 12

 

이런 결과가 나온다. 

 

8,6,3,7을 먼저 생각해 보자 

4개의 숫자 중에 어떤 숫자를 선택하든 항상 상자는 8,6,3,7 이다.

 

ex) 8번을 시작으로 선택 

8 -> 4 -> 7 -> 1 -> 8 (stop)

ex) 4번을 시작으로 선택 

4 -> 7 -> 1 -> 8 -> 4 (stop)

 

여기서 알 수 있는 성질 

1. 어떤 숫자를 선택하든 자신의 숫자로 돌아온다.

2. 시작 숫자와 시작 숫자로 돌아오면서 방문하는 숫자들을 그룹화하면 항상 동일하다.  

 

이 2가지 성질을 이용하면 된다. 

즉 bfs 처럼 풀면 된다. 

그룹화를 먼저 하고 가장 큰 그룹 2개를 선택해서 곱해주면 정답이다. 

 

해당 과정을 코드로

 

이미 그룹화된 숫자를 판별할 boolean 배열 

boolean [] visited = new boolean [cards.length + 1];

 

그룹화된 숫자을 보관할 이중 ArrayList (그룹의 개수는 다양한 케이스로 나온다.)

ArrayList<ArrayList<Integer>> group = new ArrayList<>();

 

숫자를 그룹화하기 위한 큐 

 Queue<Integer> q = new LinkedList<>();

 

그룹화 로직 

for(int i = 0; i < cards.length; i++){
    if(visited[i+1]) continue;
    visited[i+1] = true;
    ArrayList<Integer> temp = new ArrayList<>();
    q.add(i+1);
    temp.add(i+1);
    while(!q.isEmpty()){
        int cur = q.poll();
        int next = cards[cur-1];
        if(visited[next]) break;
        visited[next] = true;
        temp.add(next);
        q.add(next);
    }
    group.add(temp);
}

 

visited 배열을 통해서 이미 그룹화된(방문한) 숫자이면 continue

아니라면 방문 표시를 한다.

새로운 그룹이니까 ArrayList 생성 

큐와 ArrayList에 해당 숫자를 넣어준다.

이제 해당 숫자가 시작 숫자로 돌아올 때까지 숫자들을 bfs 진행 

bfs가 끝나면 전체 그룹에 이번에 생성한 grop을 넣어준다. 

 

 

그룹의 크기 순서대로 정렬 

Collections.sort(group, (o1, o2)->{
   return o2.size() - o1.size(); 
});

 

 

정답 retrun 

 

if(group.size() == 1) return 0;
else{
   return group.get(0).size() * group.get(1).size(); 
}

만약 그룹이 딱 1개 생성 1번 상자 그룹을 제외하고 남는 상자가 없으면 0점 반환 

아니라면 가장 큰 2개 사이즈 곱해서 반환

 

정답(전체) 코드

import java.util.*;
class Solution {
    public int solution(int[] cards) {
       
        boolean [] visited = new boolean [cards.length + 1];
        ArrayList<ArrayList<Integer>> group = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < cards.length; i++){
            if(visited[i+1]) continue;
            visited[i+1] = true;
            ArrayList<Integer> temp = new ArrayList<>();
            q.add(i+1);
            temp.add(i+1);
            while(!q.isEmpty()){
                int cur = q.poll();
                int next = cards[cur-1];
                if(visited[next]) break;
                visited[next] = true;
                temp.add(next);
                q.add(next);
            }
            group.add(temp);
        }
        Collections.sort(group, (o1, o2)->{
           return o2.size() - o1.size(); 
        });
        
        if(group.size() == 1) return 0;
        else{
           return group.get(0).size() * group.get(1).size(); 
        }
    }
}

 

읽어주셔서 감사합니다!!