[5. 배열] 5.3 임의의 두 정수값 곱하기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

[5. 배열] 단원의 기본 셋팅은 다음과 같다.

---

Q 5.3 임의의 두 정수값 곱하기

정수를 나타내는 두 개의 문자열이 주어졌을 때, 이 둘의 곱셈 결과를 반환하는 함수를 작성하라.
ex) <1,9,3,7,0,7,7,2,1>, <-7,6,1,8,3,8,2,5,7,2,8,7> => <-1,4,7,5,7,3,9,5,2,5,8,9,6,7,6,4,1,2,9,2,7>

---

곱셈이기에 단순하게 정수로 바꿔서 해결하려고 하면 오버플로우가 일어날 수 있는 크기이다.
세로로 곱셉연산하는 방법과 같이 각 자릿수에 있는 숫자를 곱한 뒤 해당 자리에 결과를 적고 마지막에 같은 자리에 있는 숫자를 모두 더하는 방법을 사용하려고 한다.
이는 m개의 부분 곱셈이 존재하고, 각 최대 n+1개의 자릿수와 곱셈연산을 수행하게 된다.

소스코드와 결과는 다음과 같다.

시간복잡도 O(nm) (n=size(num1), m=size(num2))

 

999*123 결과