[level 2] 혼자 놀기의 달인 - 131130
구분
코딩테스트 연습 > 연습문제
문제 설명
혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.
숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.
준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.
그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.
이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.
그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.
1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.
상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.
제한사항
2≤cards의 길이 ≤100cards의 원소는cards의 길이 이하인 임의의 자연수입니다.cards에는 중복되는 원소가 존재하지 않습니다.cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.
입출력 예
| cards | result |
|---|---|
| [8,6,3,7,2,5,1,4] | 12 |
입출력 예 설명
1, 4, 7, 8이 속하는 상자의 그룹과 2, 5, 6이 속하는 상자의 그룹과 3이 속하는 상자의 그룹이 존재합니다. 따라서 3번 상자를 고르지 않았을 때, 두 번의 시행에서 3과 4를 기록하며 최고 점수 12를 얻을 수 있습니다.
나의 해답
using System;
public class Solution {
public int solution(int[] cards) {
// 가장 큰 점수를 얻을 수 있는 경우의 수?
// 상자 그룹들 중에서 가장 큰 그룹 두 개를 골라서 곱하면 된다.
// 그렇다면, 문제는 이렇게 풀 수 있을 것.
// 1. 상자 그룹을 나눈다.
// 1-1. 상자 그룹은 어떻게 나누지?
// 카드의 배열의 길이와 같은 하나의 배열을 또 만들자.
// 그리고, 해당 배열을 모두 0으로 초기화를 하자.
// 1번 상자 그룹에 해당하면, 1로 값을 변경하자.
// 2번 상자 그룹에 해당하면, 2로 값을 변경하자.
// 더 나은 방법이 있을까? 해당방법은 결국 상자그룹을 나눌 때, 다시한번 배열순회가 필요하다.
// 근데 배열순회는 사실 별로 복잡도가 안커서 괜찮을듯..ok
// 2. 상자 그룹중에서 가장 큰 상자 그룹 두 개를 찾는다.
// 3. 곱한 수를 answer에 넣어서 리턴한다.
// 의문 1) 여러 개의 상자 그룹들은 항상 고정적으로 나뉘는가?
// => 상자를 여는 순서에 따라서 그룹이 바뀔 수 있을 까?
/*답은? no / why?) 항상 상자들의 안에 있는 카드들은 같은 상자그룹을 거치게 되어있다. 왜냐하면,
같은 상자그룹에 속하는 상자들은 항상 서로를 지목하고 있기 때문에 같은 상자그룹에 속하면 어느 상자를 먼저 여는지에
상관없이 같은 그룹을 갖게 된다.*/
int answer = 0;
int[] boxesArray = ClassifyBox(cards);
int[] countBox = new int[boxesArray[cards.Length]];
for(int i = 0; i < boxesArray.Length-1; i++)
{
countBox[boxesArray[i]-1]++;
}
Array.Sort(countBox);
answer=countBox[countBox.Length-1] * countBox[countBox.Length-2];
return answer;
}
public int[] ClassifyBox(int[] cards)
{
int[] groupOfBox = new int[cards.Length+1];
int groupNumber = 1;
for(int i=0; i < cards.Length; i++)
{
int startIndx = i;
if(groupOfBox[cards[startIndx]-1]==0)
{
while(groupOfBox[cards[startIndx]-1]==0)
{
groupOfBox[cards[startIndx]-1] = groupNumber;
startIndx = cards[startIndx]-1;
}
groupNumber++;
}
}
// 박스 그룹이 몇 개가 나왔는 지를 배열의 마지막에 넣어 출력
groupOfBox[cards.Length] = groupNumber;
return groupOfBox;
}
}
과정
1. 가장 먼저 제한사항을 보고 시간복잡도와 공간복잡도에 대해 생각해보았다.
caeds의 길이는 최대 100. 시간복잡도와 공간복잡도에 대해선 고려하지 않아도 될 것같다.
2. 가장 큰 점수를 얻을 수 있는 경우의 수에 대해 생각해보자.
여러 가지 자연수가 있는 곱셈에서 가장 큰 수를 얻기 위해서는 가장 큰 수와 그 다음으로 큰 수 두 개를 찾아서 곱하면 된다.
3. 문제에서 주는 규칙은
a. 각 상자안에는 카드가 들어있다.
b. 1번 상자부터 상자를 열어서 카드를 확인한다.
c. 카드에 적힌 번호에 해당하는 상자를 연다.
d. 해당 상자 안에 있는 카드를 확인한다. 이후 c로 반복.
f. 만약, 상자안의 번호가 이미 열린 상자에 해당하면 행위를 중지하고 이번에 열린 상자 그룹을 n이라고 한다.
g. 아직 열리지 않은 상자가 있다면 c부터 f까지 다시 반복하여 모든 상자를 연다.
해당 규칙을 통해 연 모든 상자들은 항상 같은 그룹을 유지하므로, 순서에 상관없이 순서를 분류하면 된다.
4. 상자를 분류하는 함수를 만들고, 해당 함수는 cards배열을 인자로 넣으면 각 배열의 인덱스는 상자번호가 되고, 요소는 해당 상자가 몇 번 상자그룹에 적혀있는지를 의미한다. 그리고 배열의 맨 끝에는 상자의 그룹이 몇 개가 존재하는 지를 나타내게 만들었다.
5. 해당 함수를 통해 상자그룹이 나뉘어져있는 배열을 얻고 해당 배열을 반복문을 통해 각 상자그룹에 몇 개의 상자가 들었는지 계산하도록 만들었다. 여기서 상자 그룹의 개수만큼 배열의 크기를 만들어 크기를 정할 수 있었다. countBox의 인덱스는 상자그룹의 번호를 나타내고, 요소는 해당 상자그룹의 상자개수를 나타낸다.
6. 우리에게 필요한 것은 상자그룹들 중 가장 많은 상자 그룹의 상자 개수와 그 다음으로 많은 상자그룹의 상자 개수이므로 오름차순으로 정렬한 후 배열의 맨 끝과 맨 끝 바로 이전의 값을 가져온 후 곱하여 답으로 제출한다.
문제점
솔직히 별로 문제될 것이 없을 정도로 쉬운문제였다.
