Programmers: 폰켓몬!

문제

• https://programmers.co.kr/learn/courses/30/lessons/1845
• 분류
  • 시간 상관 안하고 답에만 집중하면 DFS-완전탐색
  • 시간 상관 하면 Set/Hash

문제 설명

• 박사님의 폰켓몬 리스트 중에서 [리스트 사이즈] / 2개의 폰켓몬을 가지고 가고 싶다!
• 근데 같은 종류 말고 최대한 다른 종류!
• 주어지는 리스트에서 같은 숫자인 경우 = 서로 같은 종류
• 다른 숫자인 경우 = 서로 다른 종류
• i.e
  • [3, 1, 1, 2]에서 종류는 총 3가지[1, 2, 3]임!
  • 여기서 2개를 뽑아야 되니 종류를 최대로 많이 가져갈 수 있는 종류의 수 = 2 종류
    • 경우의 수도 2가지임[어떤 경우든 간에 종류의 수만 구하면 끝!]
    • 1, 3
    • 1, 2

문제 접근 / 해결 방법

DFS-완전탐색

흔히 조합과 비슷한 양상을 띄고 있어서 DFS를 이용한 완전탐색을 이용

1. 문제에서 주어는 vector num, 사용했는지 안했는지 확인하기 위한 vector used, 그리고 깊이 제한[depth_limit], 리밋에 도달했을 때 종류가 몇가지 인지 세기 위해서 추적하는 vector cur_used 정의
2. 재귀 시작 - 초기: num그대로, used=all_false, 현재 깊이=0, 깊이제한, 추적={}
3. 재귀 중, 현재 깊이가 깊이 제한과 같다면 추적 cur_used를 Set으로 만들어 Set의 사이즈를 갱신
3-1. 그게 아니라면 num을 돌면서 다음을 진행함
3-2. used 벡터에 해당 num의 원소가 쓰인다고 표시
3-3. 재귀 재시작 - num 그대로, used = 위에서 업데이트 한 내용, 현재 깊이+1, 깊이제한, 추적={num[i]}
3-4. 재귀가 끝나면 used벡터에 해당 num이 안쓰인다고 갱신

간단한 DFS 완전탐색으로 코드도 간단하겠지만, num 길이가 10,000이 될 수 있기 때문에 시간 효율이 안나서 이걸로 제출하면 틀린다.

코드

#include <vector>
#include <iostream>
#include <climits>
#include <unordered_set>

using namespace std;

int max_num = INT_MIN;

void print_vector(vector<int>& target_vector) {
    cout << "Vector: ";
    for (int tmp : target_vector) {
        cout << tmp << " ";
    }
    cout << endl;
}

unordered_set<int> convert_vector_set(vector<int>& target_vector) {
    // print_vector(target_vector);
    unordered_set<int> target_set;
    for (int tmp : target_vector) {
        target_set.insert(tmp);
    }
    return target_set;
}

void do_dfs(vector<int>& nums, vector<int> cur_use, vector<bool>& used, int depth, int limit) {
    if (depth == limit) {
        for (int i = 0; i < cur_use.size(); i++) {
            max_num = max(max_num, (int)convert_vector_set(cur_use).size());
        }
        return;
    } else {
        for (int i = 0; i < nums.size(); i++) {
            if (!used[i]) {
                vector<int> test_vec = cur_use;
                test_vec.push_back(nums[i]);

                used[i] = true;
                do_dfs(nums, test_vec, used, depth+1, limit);
                used[i] = false;
            }
        }
    }
}

int solution(vector<int> nums) {
    max_num = INT_MIN;
    vector<bool> used(nums.size(), false);
    int answer = 0;
    do_dfs(nums, {}, used, 0, nums.size() / 2);
    return max_num;
}

Set/Hash

DFS보다 코드는 훨씬 더 간결합니다. 원래 DFS연습할겸 구현해 보고 셋으로 넘어갈려 했는데 반강제로 넘어가게 됐네요 :(

1. 입력으로 들어오는 vector num을 Set으로 변경
2. 만약, set의 사이즈가 vector num.size() / 2보다 크다면 그냥 vector_num.size() / 2 를 리턴
3. 아니라면 Set 사이즈를 리턴

이는 문제[패턴]의 특성을 이용했습니다.

• 가령 입력으로 [1, 1, 2, 3, 4, 5] 라는 입력이 주어지면
  • 뽑을 수 있는 개체의 수는 6 / 2 = 3입니다.
• Set에서는 [1, 2, 3, 4, 5] 총 5개가 됩니다.
• 뽑을 수 있는 개체의 수는 최대 3개이기 때문에 해당 셋에서 아무 3개나 뽑아도 그게 최대로 고를 수 있는 종류가 됩니다.
• 다른 입력으로 [1, 1, 1, 1, 1, 1] 라는 입력이 주어지면
  • 뽑을 수 있는 개체의 수는 똑같이 3개체만 뽑을 수 있습니다.
• Set에서는 [1] 총 1개가 됩니다.
• 뽑을 수 있는 개체의 수는 최대 3개이지만, 이 경우에는 1개의 종류만 3 개체를 뽑아야 되기 때문에 1개의 종류만 뽑을 수 있습니다.

코드[최적화 전]

#include <vector>
#include <unordered_set>

using namespace std;

unordered_set<int> convert_vector_set(vector<int>& target_vector) {
    unordered_set<int> target_set;
    for (int tmp : target_vector) {
        target_set.insert(tmp);
    }
    return target_set;
}

int solution(vector<int> nums) {
    unordered_set<int> converted_set = convert_vector_set(nums);
    int set_size = converted_set.size();
    int target_size = nums.size() / 2;

    if (target_size > set_size) {
        return set_size;
    } else {
        return target_size;
    }
}

코드[최적화 후]

#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> nums) {
    unordered_set<int> converted_set(nums.begin(), nums.end());
    return min(converted_set.size(), nums.size() / 2);
}