[프로그래머스][java] lv 2 혼자 놀기의 달인

1. 문제 설명

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

혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.

숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.

준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

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

1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.

상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.

0단계 풀다가 갑자기 2단계 풀려니까 약간 눈물남

범희야! 혼자 놀지말고 보드게임 동호회나 나가라.. 왜 이런짓을 하는거니?

2. 나의 풀이

틀린 코드

    public static int solution(int[] cards) {
        int answer = 0;
        int num = cards.length -1;
        if(num % 2 == 0)
        {
        	answer = (num/2) * (num/2);  
        }
        else
        {
        	answer = ((num-1)/2) * ((num+1)/2);  
        }
        return answer;
    }

 

일단 문제 의도를 제대로 이해하지 못함.

나는 출력 결과에서부터 역산하여 생각했기 때문에, 상자 총 갯수를 구한 다음 1번째 그룹과 2번째 그룹을 균등하게 나눌 수 있다고 생각함.

하지만 이 문제에서는 상자의 연결 관계나 반복적으로 상자를 열며 그룹을 만드는 과정이 중요함.

틀린 이유 요약

1. 문제의 핵심 논리인 "상자 연결 구조"를 반영하지 않았다.
   • 상자 번호를 따라가며 그룹을 형성하는 과정을 구현하지 않았다.
2. 최대 두 그룹을 선택하는 전략을 구현하지 않았다.
   • 실제로는 가장 큰 두 그룹의 크기를 계산해 곱해야 하지만, 단순히 전체를 절반으로 나눠 계산했다.
3. 숫자와 그룹 간의 관계를 전혀 고려하지 않았다.
   • 숫자가 그룹을 결정하는 중요한 요소인데, 이를 무시하고 상자의 개수만으로 점수를 계산하려 했다.

즉 문제 해결을 위해서는 순환 구조 탐색(그래프 탐색)과 그룹 크기 계산을 구현해야 한다.

---

 

문제 핵심

• 상자에는 숫자가 들어있고, 그 숫자는 "다음에 열 상자의 번호"를 알려준다.
• 상자를 계속 열다 보면 **"반복"**이 발생합니다. 이 반복되는 상자들이 하나의 **"그룹"**.
• 여러 그룹 중 가장 큰 두 그룹을 찾아서, 이 두 그룹의 크기를 곱하면 점수.

---

어떻게 풀까?

1. 상자 그룹을 찾자.
   • 각 상자에서 출발해서, 다음 상자를 따라가며 방문한 상자들을 그룹으로 묶는다.
   • 이미 방문한 상자는 다시 처리하지 않는다.
2. 가장 큰 두 그룹을 찾자.
   • 모든 그룹의 크기를 모아 정렬한 뒤, 제일 큰 두 개를 곱한다.

---

예시

상자가 이렇게 주어졌다고 가정:
cards = [8, 6, 3, 7, 2, 5, 1, 4]

1. 상자 그룹 만들기

• 1번 상자를 열면 8이 나옴 → 8번 상자를 열면 4가 나옴 → 4번 상자를 열면 7 → 7번 상자를 열면 1
  => 그룹 1: {1, 8, 4, 7} (크기: 4)
• 남은 상자 중 2번 상자를 열면 6 → 6번 상자를 열면 5 → 5번 상자를 열면 2
  => 그룹 2: {2, 6, 5} (크기: 3)
• 남은 3번 상자는 혼자 그룹을 이룸
  => 그룹 3: {3} (크기: 1)

2. 가장 큰 두 그룹 곱하기

• 그룹 크기: 4, 3, 1
• 가장 큰 두 그룹은 4와 3 → 점수는 4 * 3 = 12

import java.util.ArrayList;
import java.util.Collections;
class Solution {
    public int solution(int[] cards) {
        int answer = 0;
        boolean[] visited = new boolean[cards.length];
        ArrayList<Integer> groupSizes = new ArrayList<>();
        
        // 각 상자 그룹을 찾는다.
        for (int i = 0; i < cards.length; i++) {
            if (!visited[i]) {
                int size = 0;
                int current = i;
                
                // 그룹의 크기 계산
                while (!visited[current]) {
                    visited[current] = true;
                    current = cards[current] - 1; // 상자 번호는 1부터 시작하므로 -1
                    size++;
                }
                
                groupSizes.add(size);
            }
        }

        // 그룹 크기를 내림차순으로 정렬
        Collections.sort(groupSizes, Collections.reverseOrder());
        
        // 가장 큰 두 그룹의 크기 곱 계산
        if (groupSizes.size() < 2) {
            answer = 0; // 그룹이 하나뿐이라면 점수는 0
        } else {
            answer = groupSizes.get(0) * groupSizes.get(1);
        }
        return answer;
    }
}

 

3. 다른 사람의 풀이

 

	public int solution(int[] cards) {
	        int n = cards.length;
	        boolean[] visited = new boolean[n];
	        List<Integer> groups = new ArrayList<>();
	
	        for (int i = 0; i < n; i++) {
	            int now = i;
	            int cnt = 0;
	            while (!visited[now]) {
	                cnt++;
	                visited[now] = true;
	                now = cards[now] - 1;
	            }
	            groups.add(cnt);
	        }
	        Collections.sort(groups, Comparator.reverseOrder());
	        return (groups.size() == 1) ? 0 : groups.get(0) * groups.get(1);
	    }

 :D 님의 풀이