문제 개요
0부터 9 사이의 숫자로 이루어진 길이 m과 n의 두 배열이 주어집니다. 두 배열에 포함된 숫자들을 조합하여 길이가 k인 가능한 한 가장 큰 수를 만들어야 하며, 이때 각 배열 내 숫자들의 상대적인 순서는 반드시 유지되어야 합니다.
예를 들어, 입력이 [3,4,7,5]와 [9,1,3,5,8,4]이고 k = 5라면, 정답은 [9,8,7,5,4]가 됩니다.
해결 전략
이 문제는 세 가지 핵심 함수로 나누어 해결할 수 있습니다.
- modify(): 스택을 활용해 하나의 배열에서 i개의 숫자를 선택했을 때 만들 수 있는 최대 부분 수열을 구합니다.
- mergeThem(): 두 개의 부분 수열을 병합하여 가장 큰 결과를 만드는 배열을 생성합니다.
- greater(): 두 배열을 사전적으로 비교하는 보조 함수입니다.
1. mergeThem() 함수
- 배열 nums1과 nums2를 받아 결과 배열 ret을 정의합니다.
- i := 0, j := 0으로 초기화하고, n은 nums1의 크기, m은 nums2의 크기로 설정합니다.
- (i < n 또는 j < m)인 동안 다음을 반복합니다.
- greater(nums1, nums2, i, j)가 참이면 ret 끝에 nums1[i]를 추가하고 i를 1 증가시킵니다.
- 그렇지 않으면 ret 끝에 nums2[j]를 추가하고 j를 1 증가시킵니다.
- ret을 반환합니다.
2. modify() 함수
- 배열 v와 정수 k를 받습니다.
- 스택 st와 결과 배열 ret을 정의합니다.
- v의 모든 원소 x에 대해 다음을 수행합니다.
- 스택이 비어 있지 않고, 스택의 top 값이 x보다 작으며, 현재 스택 크기 + 남은 원소 수 − 1이 k 이상이라면 스택에서 원소를 제거합니다.
- 스택의 크기가 k보다 작으면 x를 스택에 삽입합니다.
- 스택이 빌 때까지 top 원소를 ret에 추가하고 제거합니다.
- ret을 뒤집어 반환합니다.
3. greater() 함수
- 배열 a, b와 인덱스 i, j를 받습니다.
- (i < a.size() && j < b.size() && a[i] == b[j])인 동안 i와 j를 함께 증가시킵니다.
- j == b.size()이거나 (i < a.size() && a[i] > b[j])일 때 true를 반환합니다.
4. 메인 로직
- n := nums1의 크기, m := nums2의 크기로 설정합니다.
- i를 0부터 k까지 반복하면서, i <= n && (k − i) <= m 조건을 만족하는 경우에만 다음을 수행합니다.
- candidate = mergeThem(modify(nums1, i), modify(nums2, k − i))를 계산합니다.
- greater(candidate, ret, 0, 0)이 참이면 ret := candidate로 갱신합니다.
- 최종 ret을 반환합니다.
아래 예제 구현을 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> mergeThem(vector<int> nums1, vector<int> nums2)
{
vector<int> ret;
int i = 0;
int j = 0;
int n = nums1.size();
int m = nums2.size();
while (i < n || j < m) {
if (greater(nums1, nums2, i, j)) {
ret.push_back(nums1[i]);
i++;
}
else {
ret.push_back(nums2[j]);
j++;
}
}
return ret;
}
vector<int> modify(vector<int>& v, int k)
{
stack<int> st;
vector<int> ret;
for (int i = 0; i < v.size(); i++) {
int x = v[i];
while (!st.empty() && st.top() < x && st.size() + (v.size() - i) - 1 >= k) {
st.pop();
}
if (st.size() < k)
st.push(x);
}
while (!st.empty()) {
ret.push_back(st.top());
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
bool greater(vector<int>& a, vector<int>& b, int i, int j)
{
while (i < a.size() && j < b.size() && a[i] == b[j])
i++, j++;
return j == b.size() || (i < a.size() && a[i] > b[j]);
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
{
vector<int> ret;
int n = nums1.size();
int m = nums2.size();
for (int i = 0; i <= k; i++) {
if (i <= n && (k - i) <= m) {
vector<int> candidate = mergeThem(modify(nums1, i), modify(nums2, k - i));
if (greater(candidate, ret, 0, 0)) {
ret = candidate;
}
}
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = { 3, 4, 7, 5 }, v1 = { 9, 1, 3, 5, 8, 4 };
print_vector(ob.maxNumber(v, v1, 5));
}입력
{ 3, 4, 7, 5 }
{ 9, 1, 3, 5, 8, 4 }
5출력
[9, 8, 7, 5, 4]