[Java] 프로그래머스 131130 - 혼자 놀기의 달인

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 함수를 완성해주세요.

제한사항
2 ≤ cards의 길이 ≤ 100
cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.
cards에는 중복되는 원소가 존재하지 않습니다.
cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.

2. 문제 해석 및 아이디어

문제에 대한 나의 해석과 아이디어는 이러 했다.

1. 놀이는 총 2회 진행된다.
2. cards의 index는 박스의 일련 번호를 나타낸 것이므로 함부로 정렬 또는 변경할 수 없다.
3. 임의의 상자를 선택하고 1,2회차의 최대값을 찾아야 하므로 Brute-force 알고리즘을 선택했다.

3. 문제 풀이

전체적인 방향을 Brute-force로 잡았기 때문에 1,2회차 모두 탐색 할 이중 반복문을 사용하였다.

for (int i = 0; i < cards.length; i++) {
    ...
    for (int j = 0; j < cards.length; j++) {
    	...
    }
}

i는 1회차에 선택되는 박스의 인덱스 번호를 의미하고, j는 2회차에 선택되는 박스의 인덱스 번호를 의미한다.

 

int first = 0;
int second = 0;
boolean[] visited = new boolean[cards.length];
first = play(cards, i, visited);

boolean형의 visited 배열을 생성하고, 해당 박스가 열렸는지, 닫혔는지 판단한다.

play라는 static 메소드는 놀이의 회차가 진행되면 몇개의 상자가 열렸는지 반환한다.

first와 second 변수에는 해당 회차마다 몇개의 상자가 열렸는지 저장된다.

 

static int play(int[] cards, int index, boolean[] visited) {
    int count = 0;
    while (true) {
        if (!visited[index]) {
            visited[index] = true;
            count++;
            index = cards[index] - 1;
        } else {
            break;
        }
    }
    return count;
}

열린 상자를 만날 때 까지 반복한다.

닫힌 상자를 만났을 때는 해당 상자를 열었다는 의미로 visited를 true로 바꾸어주고,

이번 회차에 상자를 열었다는 표시로 count를 증가시켜준다.

다음 상자로 넘어가기 위해 index를 변경해준다. (상자에 담긴 번호 -1이 상자의 번호이다.)

 

for (int j = 0; j < cards.length; j++) {
    boolean[] copiedVisited = Arrays.copyOf(visited, visited.length);
    second = play(cards, j, copiedVisited);
    answer = Math.max(answer, first * second);
}

1회차가 끝났을 때의 visited 배열을 유지하기 위해 copiedVisited에 해당 visited 배열을 복사해준다.

1회차와 마찬가지로 2회차의 결과를 second 변수에 저장해주고,

first와 second를 곱한 값과 현재 answer 값을 비교하여 더 크면 answer에 저장해준다.

4. 전체 코드 보기

import java.util.Arrays;

class Solution {
    public int solution(int[] cards) {
        int answer = 0;
        for (int i = 0; i < cards.length; i++) {
            int first = 0;
            int second = 0;
            boolean[] visited = new boolean[cards.length];
            first = play(cards, i, visited);
            for (int j = 0; j < cards.length; j++) {
                boolean[] copiedVisited = Arrays.copyOf(visited, visited.length);
                second = play(cards, j, copiedVisited);
                answer = Math.max(answer, first * second);
            }
        }
        return answer;
    }

    static int play(int[] cards, int index, boolean[] visited) {
        int count = 0;
        while (true) {
            if (!visited[index]) {
                visited[index] = true;
                count++;
                index = cards[index] - 1;
            } else {
                break;
            }
        }
        return count;
    }
}

5. 후기

Greedy한 방법이 있을까 잠시 고민해보았지만, 임의로 상자를 선택한다고 하여 거침없이 Brute-force 알고리즘을 선택하였다.

상자의 개수가 100개 밖에 되지 않아 테스트케이스를 손쉽게 통과하였으나,

데이터 개수가 많아졌을 때 시간 복잡도 O(n^3)은 치명적일 수 있다.