이번엔 블랙잭 문제를 가져와봤습니다. 저번과 동일하게 코드메이트에 올려진 문제를 풀어봤습니다.

코드메이트 블랙잭 문제 링크

0. 문제 분석하기

문제를 보면 아시겠지만 우리가 만들고 싶은 건 평범한 블랙잭이 아닙니다. 평범한 블랙잭은 1 ~ 13 까지 카드가 있지만, 저희가 만들고 싶은 블랙잭은 그보다 더 높은 값을 넣어도 가능한 블랙잭입니다. 또한 답에 가까운 값도 똑같이 21이 아니라 우리가 입력한 수였으면 좋겠습니다.

하지만 공통된 부분도 있습니다. 자신이 가지고 있는 카드 중 3개를 뽑는다는 점이죠.

그럼 이러한 조건의 블랙잭을 어떻게 만들까요? 한번 생각해 봅시다.

᛫ 블랙잭 간단화 하기

1. 데이터 저장 방식 생각하기

일단 우리가 입력한 데이터를 어떻게 저장할 지 생각해 봅시다. 가장 직관적으로 생각나는 형태는 배열입니다. 하지만 무작정 배열을 사용하기엔 조금 걱정되는 부분이 있습니다. 바로 가지고 있는 총 카드의 개수이죠.

처음에 배열의 크기를 무작정 크게 선언할 수 있지만 약간 낭비인 것 같습니다. 그러므로 입력받은 수의 개수만큼만 배열을 할당해 주도록 합시다.

2. 입력받은 배열 간단화 하기

처음 데이터로 입력받아 배열로 만든 값은 그 값이 제각각입니다. 그 상태로 블랙잭을 할 수도 있지만 좀 더 깔끔했음면 좋겠습니다. 그래야 나중에 블랙잭의 이상값을 구할 때 좀 더 편할 것 같지 않나요?

여튼 입력받은 배열을 오름차순으로 정렬하는 부분을 만들도록 합시다.

3. 블랙잭의 이상값 생각하기

• 첫번째 간단화

이제 본격적으로 블랙잭을 만들려고 하는데 한가지 고민이 듭니다.

"만약 배열에서 판별할 필요없는 값이 있으면 어떻게 하지?"

예를들어 입력받은 값이 [1, 2, 3, 4, 5, 11] 인데 이상값은 12 라 해봅시다. 그렇다면 마지막 값 [11] 은 어떤 경우에도 계산할 필요 없는 값이 됩니다.
만약 이러한 경우, 값 [11] 을 빼서 생각한다면 시간도 절약되고 더 편할 것 같습니다.

그렇다면 이러한 경우를 어떻게 일반화 할 수 있을까요?

한번 배열의 최댓값과 최솟값을 고려해 생각해 봅시다.
위 경우의 특징은 "배열의 최댓값과 최솟값 2개를 더했을 때, 이미 이상값을 넘어가버린 경우" 라는 것입니다.
따라서 첫번째 간단화 논리는 "최댓값과 최솟값을 더했을 때, 이상값을 넘어간 모든 경우를 제외한다" 입니다.

• 두번째 간단화

그런데 잘 생각해보니 이러한 논리를 좀더 확장해 생각할 수 있을 것 같습니다.

두번째 예시를 보면 입력값이 [16, 85, 30, 14, 95, 63, 52, 87] 이고 이상값은 100 입니다.
위 배열을 첫번째 간단화 시키보면 [14, 16, 30, 52, 63, 85] 가 됩니다. 85 + 14 = 99 가 되기 때문에 85값은 남아있게 됩니다.

하지만 보면 알 수 있듯이 85 또한 우리가 생각하지 않아도 되는 경우입니다. 첫번째 간단화를 통해 아슬아슬 하게 넘어갔지만 두번째로 작은 값인 16 을 더하면 이상값 100 을 훌쩍 넘어가버리기 때문입니다.

따라서 이 경우도 일반화시켜 배열을 더 간단히 만들 수 있을 것 같습니다.
결국 두번째 간단화 논리는 "첫번재 간단화를 통과한 뒤, (최댓값) + (첫번째 최솟값) + (두번째 최솟값) 이 이상값을 넘어간 모든 경우를 제외한다" 가 됩니다.

1. main 함수 만들기

어느정도 블랙잭의 모양세가 만들어졌으니 한번 main 함수를 만들어 봅시다!

#include <iostream>

void sort(int *array);		// 오름차순 정렬 함수
void simplify(int *array, int ideal_value);		// 간단화 함수
int calculate(int *array, int ideal_value);	// 최종 판별 함수

int main(){
    std::cout << "\ncode_start\n\n" << std::endl;
    
    int total_num;
    int ideal_value;
    std::cin >> total_num;
    std::cin >> ideal_value;

    int *array = new int[total_num];
    for (int i = 0; i < total_num; i++) {std::cin >> array[i];}
    array[total_num] = 0;
    
    sort(array);
    simplify(array, ideal_value);

    int value = calculate(array, ideal_value);
    std::cout << value << std::endl;

    std::cout << "\n\ncode_end\n" << std::endl;
    return 0;
}

앞서 말했듯이 입력받은 수의 개수만큼 int 형 배열을 할당해 주었습니다. 그런 후 array[total_num] = 0 을 해주어 배열의 마지막을 표시해 주었습니다.
물론 char 형태로 선언하면 그럴 필요도 없을 것 같지만 뭔가 사용하기에 불안해서.. ㅎㅎ; 그냥 int 형 배열을 선언했습니다.
할당 후, 배열의 값들을 넣어주고 포인트 int 형 변수를 받는 sort 함수를 호출했습니다.
마찬가지로 포인트 int 형 변수와 우리의 이상값을 변수를 받는 simplify 함수를 호출 후, 마지막으로 계산하는 함수인 calculate 함수를 호출하였습니다.

calculate 함수가 int 형인 이유는 결국 가장 가가운 값을 출력하므로 직관적으로 값을 리턴하는 함수가 좋을 것 같아 설정하였습니다.

2. sort 함수 만들기

void sort(int *array){
    int size = 0;
    while (array[size] != 0){
        size++;
    }
    int *temp = new int[size];

    for (int i = size - 1; i >= 0; i--){
        int count = 0;
        int max = 0;
        max = array[0];
        for (int j = 0; j < size; j++){
            if (max < array[j]) {max = array[j]; count = j;}
        }
        temp[i] = max;
        array[count] = 0;
    }

    for (int i = 0; i < size; i++){
        array[i] = temp[i];
    }

    delete [] temp;
}

sort 함수에 total_num 을 인자로 받을 수도 있지만 그러긴 귀찮아서 while 문을 통해 배열의 크기 size 를 계산하였습니다. main 함수에서 array[total_num] = 0 이라 하였기 때문에 결국 size = total_num 이 됩니다.

첫번째 for 문을 보시면 항상 배열의 첫째 값을 max 로 받는걸 볼 수 있습니다. 그리고 count를 선언해 두번째 for 문에서 첫째값보다 큰 값이 나올 경우 count = j 함을 볼 수 있습니다.
결국 두번째 for 문을 빠져나오면 max 에는 남아있는 배열 중 가장 큰 값, count 는 가장 큰 값의 위치를 저장하게 됩니다. 따라서 temp의 [size - i] 즉, 마지막 값은 배열의 가장 큰 값으로 지정되고 array의 최댓값은 0으로 바뀌게 됩니다.
그러면 남아있는 array 값에 최댓값은 두번째 최댓값이 되고 이를 for 문에서 반복해 temp 배열을 완성하게 됩니다.

만약 array 배열에 0이 들어있다면 위 논리에 문제가 생기지만 우리는 블랙잭을 만들고 있기 때문에 숫자 0이 들어있을리는 업습니다!

마지막으로 array 값을 temp 에 저장된 값으로 고치면 sort 함수가 완성됩니다.

(+)
사실 이 부분은 확실하지 않아서 잘 모르겠습니다만... 마지막에 delete [] temp 부분이 필요한지 모르겠습니다. 만약 temp 가 문자열 형식이라면 맞을 것 같긴 한데... 이 부분은 공부가 더 필요한 것 같습니다.

3. simplify 함수 만들기

void simplify(int *array, int ideal_value){

    int size = 0;
    while (array[size] != 0){
        size++;
    }
    int test;
    int maximum, minimum = array[0];
    int count = 1;

    for (int i = size - 1; i >= 0; i--){
        count++;
        int testing = 0;
        maximum = array[i];
        test = maximum + minimum;
        if (test >= ideal_value) {array[i] = 0; testing = 1;}
        else if (test + array[1] > ideal_value) {array[i] = 0; testing = 1;}

        if (testing == 0) break;
        
    }

    int *temp = new int[count];
    for (int i = 0; i < count; i++){
        temp[i] = array[i];
    }
    array = new int[count];
    for (int i = 0; i < count; i++){
        array[i] = temp[i];
    }

    delete [] temp;
}

sort 함수를 통해 배열은 오름차순으로 정렬되었습니다. 때문에 배열 중 최솟값은 무조건 array[0], 두번째 최솟값은 array[1] 이 됩니다.
또한 test = maximum + minimum 을 하여 (최댓값) + (최솟값) 을 가지도록 하였습니다.

for 내의 첫번째 if 문은 첫번째 간단화 조건입니다. (최댓값) + (최솟값) 이 이상값을 넘어갈 때, 그때의 최댓값은 고려할 필요가 없으므로 array[i] = 0 을 하여 0으로 만들었습니다.
두번째 else if 문은 두번째 간단화 조건입니다. (최댓값) + (최솟값) + (두번째 최솟값) 이 이상값을 넘어가는 경우므로 똑같이 0 으로 만들었습니다.

만약 위 조건문에 걸리지 않은 경우, 모든 간단화를 마친 경우이므로 더이상 for 문을 돌릴 필요가 없습니다. 때문에 각 조건문에 testing = 1 을 넣었고 두 조건에 걸리지 않는다면 testing = 0 이 되기 때문에 for 문이 멈추게 됩니다.

(+)
나머지 코드의 의도는 처음 선언한 array 의 크기를 줄여보려는 의도였습니다. 하지만 의도대로 돌아간 지는...? 잘 모르겠습니다. ㅎㅎ;
조금이라도 memory leak 를 막아보려는 의도였는데, 이러한 경우는 뭔가 char 형태의 배열에만 해당되는 것 같기도 하고...? 아닌 것 같기도 하고...? 좀더 공부가 필요한 것 같습니다.

4. calculate 함수 만들기

이제 마지막 부분입니다. 하지만 정작 앞선 부분에서 결국 어떻게 값을 판별할지 생각하지 않았습니다. 한번 답변 예시와 함께 생각해봅시다.

᛫ 답 판별하는 논리 생각하기

두번째 예시를 한번 생각해봅시다.
sort, simplify 함수를 거치면 두번째 예시는 [14, 16, 30, 52, 63] 가 됩니다. 여기서 가장 이상적인 값은 무엇일까요?

일단 정답은 98 입니다. [16 + 30 + 52] 하여 이상값 100 에 가장 가까운 수가 됩니다. 이번에도 최댓값과 최솟값을 통해 생각해 봅시다.

우리가 답을 생각할 때, 일단 가장 큰 값들을 모두 더해봅니다. [30 + 52 + 63] = 145 이므로 이 경우는 이상값을 넘어갑니다. 그 다음 생각하는 경우는 [16 + 52 + 63] 입니다. 이 또한 131 이므로 맞지 않습니다. 마지막으로 [14 + 52 + 63] 을 생각하고 이 또한 맞지 않으므로 다음 큰 경우를 생각하게 됩니다.

무언가 패턴이 보이지 않나요? 위 경우에서는 항상 [52 + 63] 을 짝지어서 생각하고 있습니다. 즉, 배열에서 가장 큰 값과 그 다음으로 큰 값을 짝지어서 생각하고 있다는 겁니다. 그런 다음 만약 조건에 맞지 않으면 그 다음 짝인 [30 + 52] 에 대해 생각할 것입니다.

따라서 우리는 이와같은 논리를 생각할 수 있습니다.
"(최댓값) + (두번째 최댓값) 을 짝찌은 다음 남은 배열에서 큰 순으로 더해본다. 모두 더한 값이 이상값보다 작거나 같으면 그 값이 가장 가까울 값 중 하나일 것이다."
이를 바탕으로 코드를 짜봅시다.

᛫ 코드 만들기

int calculate(int *array, int ideal_value){
    int size = 0;
    while (array[size] != 0){
        size++;
    }

    int *value = new int[(size) * (size - 1) * (size - 2) / 6];
    int count = 0;

    int first, second;
    for (int i = size - 1; i >= 0; i--){
        first = array[i];
        second = array[i - 1];

        int test = ideal_value - (first + second);
        // 마지막 이상적인 원소 값

        for (int j =  i - 2; j >= 0; j--){
            if (test - array[j] >= 0) {
            value[count] = first + second + array[j];
            count++;
            break;
            }
        }
        if (value[count - 1] == ideal_value) break;
    }

    int max = value[0];
    for (int i = 1; i < count; i++){
        if (max < value[i]) max = value[i];
    }

    delete [] value;

    return max;
}

일단 계산해서 나온 값들을 저장할 value 를 선언했습니다. 경우의 수를 생각해 봤을 때 array 원소 조합의 개수는 (size)C3 이 되므로 value의 크기를 [(size) x (size - 1) x (size - 2) / 6] 로 지정했습니다.

첫번째 최댓값을 저장할 first, 두번째 second 를 선언하였고 이상값과 이 둘을 더한값을 뺀 test 를 선언하였습니다.

첫번째 if 문에서 test - array[j] >= 0 을 하여 위에서 말한 조건에 맞는지 확인하고, 그 값을 value 에 저장합니다.
만약 value 에 저장한 값이 이상값과 같다면 더이상 볼 필요가 없으므로 for 문에서 나가도록 지정했습니다.

마지막으로 value에 넣은 값들 중 가장 큰 값이 max 가 되도록 하였습니다.

5. 모두 합치기

이제 모든 함수를 만들었으니 다 합쳐 봅시다.

#include <iostream>

// 블랙잭 업그레이드 버전

void sort(int *array);
void simplify(int *array, int ideal_value);
int calculate(int *array, int ideal_value);

int main(){
    std::cout << "\ncode_start\n\n" << std::endl;
    
    int total_num;
    int ideal_value;
    std::cin >> total_num;
    std::cin >> ideal_value;

    int *array = new int[total_num];
    for (int i = 0; i < total_num; i++) {std::cin >> array[i];}
    array[total_num] = 0;
    
    sort(array);
    simplify(array, ideal_value);

    int value = calculate(array, ideal_value);
    std::cout << value << std::endl;

    std::cout << "\n\ncode_end\n" << std::endl;
    return 0;
}

void sort(int *array){
    int size = 0;
    while (array[size] != 0){
        size++;
    }
    int *temp = new int[size];

    for (int i = size - 1; i >= 0; i--){
        int count = 0;
        int max = 0;
        max = array[0];
        for (int j = 0; j < size; j++){
            if (max < array[j]) {max = array[j]; count = j;}
        }
        temp[i] = max;
        array[count] = 0;
    }

    for (int i = 0; i < size; i++){
        array[i] = temp[i];
    }

    delete [] temp;
}
void simplify(int *array, int ideal_value){
    int size = 0;
    while (array[size] != 0){
        size++;
    }
    int test;
    int maximum, minimum = array[0];
    int count = 1;

    for (int i = size - 1; i >= 0; i--){
        count++;
        int testing = 0;
        maximum = array[i];
        test = maximum + minimum;
        if (test >= ideal_value) {array[i] = 0; testing = 1;}
        else if (test + array[1] > ideal_value) {array[i] = 0; testing = 1;}

        if (testing == 0) break;
        
    }

    int *temp = new int[count];
    for (int i = 0; i < count; i++){
        temp[i] = array[i];
    }
    array = new int[count];
    for (int i = 0; i < count; i++){
        array[i] = temp[i];
    }

    delete [] temp;
}

int calculate(int *array, int ideal_value){
    int size = 0;
    while (array[size] != 0){
        size++;
    }

    int *value = new int[(size) * (size - 1) * (size - 2) / 6];
    int count = 0;

    int first, second;
    for (int i = size - 1; i >= 0; i--){
        first = array[i];
        second = array[i - 1];

        int test = ideal_value - (first + second);
        // 마지막 이상적인 원소 값

        for (int j =  i - 2; j >= 0; j--){
            if (test - array[j] >= 0) {
            value[count] = first + second + array[j];
            count++;
            break;
            }
        }
        if (value[count - 1] == ideal_value) break;
    }

    int max = value[0];
    for (int i = 1; i < count; i++){
        if (max < value[i]) max = value[i];
    }

    delete [] value;

    return max;
}

이제 우리가 원하는 블랙잭이 완성되었습니다!

6. 총평

저번에 가져온 스도쿠 문제보다 유익했던 것 같습니다. 그냥 무작정 값들을 모두 더해보며 계산할 수 있었지만 좀 더 효율적으로 배열을 간단화 시켰고, 이를 토대로 이상값과 가장 가까운 값을 얻을 수 있었습니다.

비록 class 같은 C++ 문법(?)을 사용하진 않았지만 블랙잭 조건을 간단화 시키는 과정이 유익했던 것 같습니다.

다음 포스팅으로 뵙겠습니다. 감사합니다.