문제설명
문자열로 입력받은 데이터로 곱셈 로직을 구현하기
전략
내 전략
// TODO:
// 곱하기 알고리즘
// 목표: 곱하기 결과 출력하기
// 단계
// 메모리를 준비한다
// 각자리수마다 곱하기를 한 후 메모리에 넣는다
// 첫번째자리부터 마지막자리까지 진행
// 첫번째 자리와 첫번째 자리를곱한다
// 10으로 나눈 나머지를 해당 자리 자릿수에 더한다
// 10으로 나눈 몫은 다음 자릿수에 더한다
// 다음 자릿수에 더한값 또한 넘치면 연쇄반응이 멈출 때까지 더하기
// 다음수를 진행한다
// 배열 자체를반환한다
모범전략
1. 문자열 str1, str2를 입력받는다.
2. 두 문자열의 곱셈 결과를 저장할 배열 result를 준비한다.
- 배열 크기는 (str1의 길이 + str2의 길이)로 설정한다.
- 배열은 '0'으로 초기화한다.
3. 각 자리 숫자에 대해 곱셈을 수행한다:
- str2의 마지막 자리부터 첫 번째 자리까지 반복:
- str1의 마지막 자리부터 첫 번째 자리까지 반복:
- 현재 자리 숫자(str2[i]와 str1[j])를 곱한다.
- 결과를 result 배열의 적절한 위치에 추가한다.
- 위치 계산: i + j + 1
- 나머지(%)는 현재 자리(result[i + j + 1])에 저장.
- 몫(/)은 carry로 저장하여 다음 자리로 넘긴다.
4. carry를 처리한다:
- carry가 0이 아닐 경우, 다음 자리로 연쇄적으로 더한다.
- carry 전파가 끝날 때까지 반복한다.
5. 결과 배열에서 앞부분의 불필요한 '0'을 제거한다.
- 배열의 첫 번째 '0'이 아닌 위치를 찾는다.
- 결과가 모두 '0'이라면 "0"을 반환한다.
6. 결과 배열을 문자열로 변환하여 반환한다.
구현
나의 코드
string Multiply(string str1, string str2) {
if(!str1.size() || !str2.size()){
return 0;
}
// TODO:
// 곱하기 알고리즘
// 목표: 곱하기 결과 출력하기
// 단계
// 메모리를 준비한다
// 각자리수마다 곱하기를 한 후 메모리에 넣는다
// 첫번째자리부터 마지막자리까지 진행
// 첫번째 자리와 첫번째 자리를곱한다
// 10으로 나눈 나머지를 해당 자리 자릿수에 더한다
// 10으로 나눈 몫은 다음 자릿수에 더한다
// 다음 자릿수에 더한값 또한 넘치면 연쇄반응이 멈출 때까지 더하기
// 다음수를 진행한다
// 배열 자체를반환한다
string result(str1.size() + str2.size(), '0');
for(int i = str2.size() - 1; i >= 0; i--){
int loc = result.size() - 1 + (i + 1 - str2.size());
for(int j = str1.size() - 1; j >=0; j--){
int mul = (str1[j] - '0') * (str2[i] - '0');
int carry = mul / 10;
int remain = mul % 10;
// 더하는 과정 자체가 랙이 걸리는 경우가 발생한다
int mid_sum = (result[loc] - '0' + remain);
if(mid_sum >= 10){
carry += 1;
mid_sum %= 10;
}
result[loc] = mid_sum + '0';
// TODO: carry 자체가 9가 되는 경우가 있다, 받는 수가 9일 때 또 넘겨야하는 상황이 발생한다
cout << "mul: " << mul << ", carry: " << carry << ", remain: " << remain << ", result: " << result << ", loc: " << loc << endl;
int temp = loc - 1 -(str1.size() - 1 - j);
cout << "temp: " << temp << endl;
while(carry != 0){
int mid_carry = carry + (result[temp] - '0');
carry = mid_carry / 10;
result[temp] = (mid_carry % 10) + '0';
temp--;
cout << "mul: " << mul << ", carry: " << carry << ", remain: " << remain << ", result: " << result << ", loc: " << loc << endl << endl;
}
// result[loc - 1] = ((result[loc - 1] - '0') + carry) + '0';
cout << "mul: " << mul << ", carry: " << carry << ", remain: " << remain << ", result: " << result << ", loc: " << loc << endl << endl;
loc--;
}
}
int check = 0;
while(result[check] =='0'){
check++;
};
result = result.substr(check);
return result;
}
모범코드
string Multiply(string str1, string str2) {
if (str1.empty() || str2.empty()) {
return "0";
}
string result(str1.size() + str2.size(), '0');
// 각 자리수마다 곱하기
for (int i = str2.size() - 1; i >= 0; i--) {
int carry = 0;
for (int j = str1.size() - 1; j >= 0; j--) {
// 현재 자리수 곱하기
int mul = (str2[i] - '0') * (str1[j] - '0');
int sum = mul + (result[i + j + 1] - '0') + carry;
// 현재 자리 업데이트
result[i + j + 1] = (sum % 10) + '0';
carry = sum / 10;
}
// 남은 carry 처리
result[i] += carry;
}
// 결과 문자열 앞의 0 제거
size_t start = result.find_first_not_of('0');
if (start == string::npos) {
return "0"; // 모든 값이 0인 경우
}
return result.substr(start);
}
내가 생각못했던 것들
- 변수 2개의 관계만 고려했다. 모범코드에서는 3개 이상을 고려하면서 코드를 깔끔하게 정리했다. 변수들간의 관계를 전체 시스템에서 관찰해야했다.
- 하나의 함수 내에서 로직을 짤 때도 로직을 부분으로 나눠서 작성하자. 각 로직 별로 입출력을 나눠 단계별로 생각을하면 덜 꼬인다.
좋은 의사코드 작성 가이드
- 구체적으로 작성하되, 세부 구현은 추상화:
- 지나치게 코드처럼 작성하지 말고, 로직 중심으로 작성합니다.
- 예를 들어:
- 나쁨: result[i + j + 1] = (result[i + j + 1] - '0') + ...
- 좋음: "곱셈 결과를 result[i + j + 1]에 저장한다."
- 단계별로 나눠 작성:
- 한 번에 많은 일을 하지 말고, 각 단계가 독립적으로 보이게 작성합니다.
- 현재 의사코드는 단계가 명확히 나뉘어 있어 좋은 예입니다.
- 복잡한 부분은 예시 추가:
- carry 전파와 같은 복잡한 로직은 한두 줄로 끝내지 말고, 추가 설명이나 예시를 넣습니다.
- 예:
- plaintext 코드 복사 carry가 발생하면: - result[i + j] += carry - carry = result[i + j] / 10 - result[i + j] %= 10
- 엣지 케이스 다루기:
- 입력 문자열이 "0"이거나, 빈 문자열일 경우 처리 방식을 명시적으로 작성합니다.
- 읽기 쉽게 포맷팅:
- 주석처럼 작성하기보다는, 플레인 텍스트 형식으로 로직을 기술합니다.