[프로그래머스/C++] 혼자 놀기의 달인

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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번 상자에 담긴 카드에 적힌 숫자를 의미합니다.

 

풀이

입출력 예시

 

풀이

먼저 문제에 적힌 내용들을 정리하면,

 

1. 숫자가 적힌 카드의 배열 cards가 정렬되지 않은 상태로 주어진다.

2. cards 배열은 cards 배열 길이 이하의 자연수로만 중복 없이 구성되어있다.

3. cards 배열에서 한 원소를 선택하면, 원소 번째 상자를 연다.

4. 만약 그 상자가 이미 열린 상자라면 상자 열기를 멈추고 이때까지 연 상자들은 하나의 그룹이 된다.

5. 상자를 닫지 말고 위 과정을 한번 더 거쳐서 하나의 그룹을 더 얻는다.

6. 두 그룹의 상자의 수를 곱해준 값이 점수가 된다. 점수의 최댓값을 구하라.

 

이제 문제를 풀때다.

cards 배열의 길이가 100 이하이므로 완전 탐색을 해서 풀 수 있는 문제다.

재귀를 이용해 계속 상자를 열어가면서 연 상자들을 각 그룹에 저장해준다.

 

1. 모든 카드들에 대하여

2. 카드 하나를 선택해 그 상자를 열어 첫 번째 그룹을 만든다.

2 - 1. 상자를 열어 나온 카드의 번호에 해당되는 상자를 가져온다.

2 - 2. 그 상자가 열리지 않은 것이라면 열고, 그렇지 않으면 상자 열기를 그만둔다.

3. 다음으로 다른 카드 하나를 선택, 2번 과정을 또 진행해 두 번째 그룹을 만든다.

3 - 1. 다른 경우를 구해야 하므로 연 상자는 다시 닫아준다.

4. 가장 높은 점수를 구한다.

 

이미 연 상자를 판별하기 위한 배열을 선언하는 것, 다른 경우를 찾기 위해 이 배열을 초기화해주는 것을 잊지 않으면 구현은 생각보다 간단하다.

 

#include <string>
#include <vector>

using namespace std;

bool opened[100];
vector<int> Cards;
vector<vector<int>> box(2);

void select(int card, int box_num) {
    // 카드에 적힌 번호의 상자를 개봉하지 않았다면
    if (!opened[card - 1]) {
        
        // 현재 그룹의 상자에 그 상자 번호를 저장
        box[box_num].push_back(card - 1);
        opened[card - 1] = true;
        
        // 현재 상자의 카드 번호를 통해 다시 판별
        select(Cards[card - 1], box_num);
        
        // 두 번째 그룹의 다른 경우를 체크하기 위해 연 상자를 다시 닫음
        if (box_num == 1) {
            opened[card - 1] = false;
        }
    }
}

int solution(vector<int> cards) {
    int answer = 0;
    Cards = cards;
    
    // 첫 번째 그룹 시작
    for (int i = 0; i < cards.size(); i++) {
        opened[i] = true;
        box[0].push_back(i);
        
        // 첫 번째 그룹 모으기
        select(cards[i], 0);
        
        // 두 번째 그룹 시작
        for (int j = 0; j < cards.size(); j++) {
            if (!opened[j]) {
                opened[j] = true;
                box[1].push_back(j);
                
                // 두 번째 그룹 모으기
                select(cards[j], 1);
                
                // 점수 계산 후 더 큰 점수 저장
                answer = max(answer, (int)(box[0].size() * box[1].size()));
                
                // 다른 경우도 찾아야 하므로 초기화.
                opened[j] = false;
                box[1].clear();
            }
        }
        box[0].clear();
        for (int i = 0; i < cards.size(); i++) {
            opened[i] = false;
        }
    }
    
    return answer;
}