글 읽기 - 긴 자리 계산 질문입니다

cubalys 6년 전 0

string으로 덧셈 뺄셈 곱셈 구현했습니다

곱셈이가장 오래 걸리긴 하지만

그래도 N제곱이기 때문에 시간복잡도 상으로 전혀 문제가 없을 것으로 예상했는데

시간초과가 나네요

같은 함수를 사용해

큰 수 계산

문제는 맞았습니다! 를 받은 것으로 봐서는 함수 자체가 틀린거 같지는 않은데

어떤 부분에서 문제가 생긴 것인지 궁금합니다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
string set[] = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10" }, mod;
string remove_0(string);
int strCMP(string, string);
string sum(string, string, int, int, int);
string sum(string, string);
string sub(string, string, int, int);
string sub(string, string);
string mul(string, string, int, int, int);
string mul(string, string);
int main(){
	string A, B;
	cin >> A >> B;
	cout << sum(A, B) << endl << sub(A, B) << endl << mul(A, B) << endl;
}
string remove_0(string x){
	int xlen = x.size();
	for (int i = 0; i < xlen; i++)
		if (x[i] != '0')
			return x.substr(i, xlen - i);
	return "0";
}
int strCMP(string x, string y){
	x = remove_0(x);
	y = remove_0(y);
	int xlen = x.size(), ylen = y.size();
	if (xlen > ylen) return 1;
	if (ylen > xlen) return -1;
	for (int i = 0; i < xlen; i++){
		if (x[i] > y[i])
			return 1;
		if (y[i] > x[i])
			return -1;
	}
	return 0;
}
string sum(string x, string y, int c, int xlen, int ylen){
	if (xlen + ylen + c == 0) return "";
	int a = xlen == 0 ? 0 : x[xlen - 1] - '0', b = ylen == 0 ? 0 : y[ylen - 1] - '0';
	int nxlen = xlen == 0 ? 0 : xlen - 1, nylen = ylen == 0 ? 0 : ylen - 1;
	return sum(x.substr(0, xlen - 1), y.substr(0, ylen - 1), (a + b + c) / 10, nxlen, nylen) + set[(a + b + c) % 10];
}
string sum(string x, string y){
	if (x[0] == '-' && y[0] == '-')
		return "-" + sum(x.substr(1, x.size() - 1), y.substr(1, y.size() - 1));
	if (x[0] == '-')
		return sub(y, x.substr(1, x.size() - 1));
	if (y[0] == '-')
		return sub(x, y.substr(1, y.size() - 1));
	int xlen = x.size(), ylen = y.size();
	return sum(x, y, 0, xlen, ylen);
}
string sub(string x, string y, int xlen, int ylen){
	if (xlen + ylen == 0) return "";
	int a = xlen == 0 ? 0 : x[xlen - 1] - '0', b = ylen == 0 ? 0 : y[ylen - 1] - '0';
	if (a < b){
		for (int i = xlen - 2; i >= 0; i--)
			if (x[i] != '0'){
				x[i]--; break;
			}
			else x[i] = '9';
			a += 10;
	}
	int nxlen = xlen == 0 ? 0 : xlen - 1, nylen = ylen == 0 ? 0 : ylen - 1;
	return remove_0(sub(x.substr(0, xlen - 1), y.substr(0, ylen - 1), nxlen, nylen) + set[a - b]);
}
string sub(string x, string y){
	if (x[0] == '-' && y[0] == '-')
		return sub(y.substr(1, y.size() - 1), x.substr(1, x.size() - 1));
	if (x[0] == '-')
		return "-" + sum(x.substr(1, x.size() - 1), y);
	if (y[0] == '-')
		return sum(x, y.substr(1, y.size() - 1));
	if (strCMP(x, y) == -1)
		return "-" + sub(y, x);
	int xlen = x.size(), ylen = y.size();
	return sub(x, y, xlen, ylen);
}
string mul(string x, string y, int c, int xlen){
	if (xlen == 0 && c == 0) return "";
	int a = xlen == 0 ? 0 : x[xlen - 1] - '0', b = y[0] - '0';
	int nxlen = xlen == 0 ? 0 : xlen - 1;
	return mul(x.substr(0, xlen - 1), y, (a * b + c) / 10, nxlen) + set[(a * b + c) % 10];
}
string mul(string x, string y){
	if (x[0] == '-' && y[0] == '-')
		return mul(x.substr(1, x.size() - 1), y.substr(1, y.size() - 1));
	if (x[0] == '-' || y[0] == '-')
		return "-" + mul(x.substr((x[0] == '-'), x.size() - (x[0] == '-')), y.substr((y[0] == '-'), y.size() - (y[0] == '-')));
	int ylen = y.size(), xlen = x.size();
	vector <string> res;
	for (int i = ylen - 1, j = 0; i >= 0; i--, j++){
		res.push_back(mul(x, y.substr(i, 1), 0, xlen));
		for (int k = 0; k < j; k++)
			res[j] += "0";
	}
	int reslen = res.size();
	string ret = "0";
	for (int i = 0; i < reslen; i++)
		ret = sum(ret, res[i]);
	return ret;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

긴 자리 계산 질문입니다

cubalys 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말