문제 설명
이 문제는 두 개의 배열 a[]와 b[]의 요소를 더하는 것이지만, 결과값이 특정 제약 조건에 따라 달라지는 것이 특징입니다. 두 배열의 합은 세 번째 배열 c[]에 저장되는데, 이때 각 요소는 반드시 한 자리 수여야 합니다.
만약 두 요소의 합이 두 자리 이상이라면, 그 숫자를 자릿수별로 분할하여 여러 개의 한 자리 수 요소로 나누어 저장합니다. 예를 들어 두 요소의 합이 27이라면, 세 번째 배열에는 27이 아닌 2, 7로 분할되어 저장됩니다.
입력: a[] = {1, 2, 3, 7, 9, 6}
b[] = {34, 11, 4, 7, 8, 7, 6, 99}
출력: 3 5 1 3 7 1 4 1 7 1 3 6 9 9접근 방법
문제 해결 과정은 다음과 같습니다.
먼저 출력 배열을 준비한 뒤, 두 배열의 0번째 인덱스부터 동시에 루프를 실행합니다. 루프의 각 반복마다 두 배열에서 다음 요소를 하나씩 가져와 더합니다. 이때 합이 9보다 작거나 같으면 그 값을 그대로 출력 배열에 추가하고, 합이 10 이상이면 각 자릿수를 분할하여 순서대로 출력 배열에 추가합니다.
공통 인덱스에 대한 처리가 끝나면, 길이가 더 긴 배열의 남은 요소들도 동일하게 검사하여 한 자리 수는 그대로, 두 자리 이상의 수는 자릿수별로 분할해 출력 배열에 추가합니다.
구현 예제 (C++)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
// 숫자 n을 자릿수별로 분할하여 벡터 c에 추가하는 함수
void split(int n, vector<int> &c) {
vector<int> temp;
while (n) {
temp.push_back(n % 10);
n = n / 10;
}
c.insert(c.end(), temp.rbegin(), temp.rend());
}
// 두 배열을 조건에 맞게 더하는 함수
void addArrays(int a[], int b[], int m, int n) {
vector<int> out;
int i = 0;
// 두 배열의 공통 인덱스 구간 처리
while (i < m && i < n) {
int sum = a[i] + b[i];
if (sum < 10) {
out.push_back(sum); // 한 자리 수면 그대로 추가
} else {
split(sum, out); // 두 자리 이상이면 자릿수 분할
}
i++;
}
// 첫 번째 배열의 남은 요소 처리
while (i < m) {
split(a[i++], out);
}
// 두 번째 배열의 남은 요소 처리
while (i < n) {
split(b[i++], out);
}
for (int x : out)
cout << x << " ";
}
int main() {
int a[] = {1, 2, 3, 7, 9, 6};
int b[] = {34, 11, 4, 7, 8, 7, 6, 99};
int m = 6;
int n = 8;
addArrays(a, b, m, n);
return 0;
}동작 과정 살펴보기
위 예제 입력의 경우 다음과 같이 진행됩니다.
- 1 + 34 = 35 → 3, 5로 분할
- 2 + 11 = 13 → 1, 3으로 분할
- 3 + 4 = 7 → 한 자리 수이므로 7 그대로 저장
- 7 + 7 = 14 → 1, 4로 분할
- 9 + 8 = 17 → 1, 7로 분할
- 6 + 7 = 13 → 1, 3으로 분할
- 배열 a가 먼저 소진되었으므로 배열 b의 남은 요소 6 → 6, 99 → 9, 9
복잡도 분석
시간 복잡도: O(m + n). 두 배열을 한 번씩만 순회하며, 각 숫자의 자릿수 분할 역시 상수 시간 내에 처리됩니다.
공간 복잡도: O(결과 배열의 크기). 출력 배열은 입력 배열보다 커질 수 있는데, 이는 두 자리 이상의 숫자가 여러 개의 요소로 분할되기 때문입니다.