A * B

---

A * B를 large-scale에서 수행하려면 어떻게 해야할까?
5 * 5 같은건 인터넷에서 검색해도 간단하게 수행할 수 있을 것이다.

그렇다면 10억 * 10억은? int를 초과할태니 double을 쓰면 되지 않을까?
그렇게 생각하고 double을 사용해봤다.

int main() {
	double val_a, val_b
	...
    
    cout << to_string(val_a * val_b) << "\n"
    return 0;
}

꼴에 Double이라고 출력값은 11418858.000000 처럼 붙어나옴..
그럼 string lib을 잘 만져서 뒤쪽을 잘라주면 될거다.

따로 String을 할당하고 "."를 파싱해서 잘라보자

#include <iostream>
#include <sstream>
#include <string>


int main() {
    double val_a, val_b;
    char delim = '.';

    scanf("%lf %lf", &val_a, &val_b);

    std::string result;
    std::istringstream res;

    res.str(std::to_string(val_a * val_b));
    
    getline(res, result, delim);
    std::cout << result << "\n";

    return 0;
}

위 코드로 double의 입력범위와 출력범위까지는 대응할 수 있다.
그렇다면 double의 입출력범위를 넘는 수가 들어오는 경우에는 어떻게 해결해야 할까?
또 Double은 표현의 한계가 존재한다. IEEE754에서 Double의 구조를 생각해보면 Fragment의 자릿수가 만들어내는 표현의 한계라는 말의 뜻을 알 수 있을 것이다. 이를 해결하려면?
이제부터 문제가 좀 골때리기 시작한다.

이 문제를 3가지의 Task로 나누어 생각해보자.

1. 임의의 0 이상의 정수를 입력받는다.
2. 임의의 0 이상의 정수 2개를 곱한 것을 저장한다.
3. 임의의 0 이상의 정수를 출력한다.

일단 임의의 큰 수라면, 해당 수를 Numeric 형식의 자료형에 담을 수 없을 것이다.
미리 크기가 정해진 자료형의 경우 임의의 큰 수에 대해서 대응할 수 없다. 그렇다면 변동이 가능하면서 원하는 값을 저장할 수 있는 기본 자료형을 생각해보면 Vector, String, *Char가 있다.

좋은 개발자라면 선택에 이유가 있어야 한다던데.. 나는 나쁜 개발자라서 사실 잘 모르겠다. 일단 풀이를 생각해보자. 내가 간단하게 생각한 풀이는

1. 특정 개수의 숫자 단위마다 String을 끊어서 저장한 후 각각을 곱해주기
2. 하나의 수를 어떻게든 저장해놓고 digit마다 곱해가면서 iterative하게 더해주기.

둘다 귀찮아보인다... 하지만 2번의 과정이 조금 더 직관적으로 보임으로 해당 문제로 진행해보자. 우선 임의의 큰 수 임 A, B를 string에 저장할 수 있을 것이다. 그럼 str_a에 해당 값을 고정해놓고 str_b에 대해서 하나의 digit씩 뒤에서 앞으로 움직이며 곱해서 각각의 자릿수에 맞는 수를 저장한다.

쓰고보니 자릿수마다 저장할 수 있는 저장소가 있으면 나중에 다시 string으로 만들 때 편하지 않을까? dict을 만들어서 1의 자리는 dict[1], 10의 자리는 dict[2]에 vector<int>로 저장해 놓자.
이후에는 dict의 key값을 1씩 증가시켜가며 순서대로 돌면서 저장된 vector 내부의 int의 모든 값을 sum 하고 해당 경우 10이 넘어서 올림이 발생한다면 그것만 잘 처리해주면 된다.

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <numeric>

using namespace std;

map< string, vector<int> > digit_map;


int main() {
    string input_str, val_a, val_b, map_key;
    getline(cin, input_str);

    char delimeter = ' ';
    int int_d_a, int_d_b, temp_res, temp_remain;

    istringstream input_stream;
    input_stream.str(input_str);

    getline(input_stream, val_a, delimeter);
    getline(input_stream, val_b, delimeter);

    // std::cout << val_a << "\n" << val_b << "\n";

    int digit_idx = 0;

    for (int i = val_a.size() - 1; i >= 0; i--) {
        int_d_a = val_a[i] - 48;
        for (int j = val_b.size() - 1; j >= 0; j--) {
            int_d_b = val_b[j] - 48;
            ...
            }
        }
        digit_idx += 1;
    }
    temp_res = 0;

    string result_str = "";

    int max_length = val_a.size() + val_b.size();
    for (int k = 0; k < max_length; k++) {
        string k_key = to_string(k);
        vector<int> digit_vec = digit_map[k_key];
        temp_res = accumulate(digit_vec.begin(), digit_vec.end(), 0);
        temp_remain = temp_res % 10;
        result_str = to_string(temp_remain) + result_str;

        temp_res = temp_res / 10;
        int remain_idx = 1;
        while (temp_res >= 1) {
            temp_remain = temp_res % 10;
            ...
        }
    }

    std::cout << result_str << "\n";

    return 0;
}

어캐 요래요래 짜니까 되긴 하더라...
별로 안이쁘긴 한데 내 자식이니 어쩔수없고 ㅋㅋ
이렇게 짜니 맨 앞자리가 0일때가 가끔 생겨서 해당 부분만 추가적으로 strcmp 등 string lib 함수로 없애주면 되더라.

다 안올려놓는 이유는 성격이 나빠서ㅋ 대학교 과제에 쓰지말라고ㅋ

근데 역시 못생기게 짜서 그런지 시간이 좀 오래걸린다..
시간 최적화는 내일