문제 설명
정수로 이루어진 배열 nums가 주어졌다고 가정해 보겠습니다. 우리는 이 배열에 다음과 같은 연산을 수행할 수 있습니다. 각 연산에서는 nums[i]를 하나 골라 삭제하고, 그 대가로 nums[i]만큼의 점수를 얻습니다. 단, nums[i] - 1 또는 nums[i] + 1과 값이 같은 모든 원소도 함께 삭제해야 합니다. 초기 점수는 0이며, 이러한 연산을 통해 얻을 수 있는 최대 점수를 구하는 것이 목표입니다.
예를 들어 입력이 [3,4,2]라면 출력은 6이 됩니다. 먼저 4를 삭제하면 4점을 얻게 되고, 조건에 따라 3도 함께 삭제됩니다. 이후 남은 2를 삭제해 2점을 추가하면 총 6점을 획득할 수 있습니다.
접근 방법
이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. C++의 map은 키를 기준으로 자동 정렬되므로, 숫자를 오름차순으로 순회하면서 각 숫자를 '선택하는 경우'와 '선택하지 않는 경우'의 최대 점수를 누적 비교하면 됩니다.
구체적인 해결 단계는 다음과 같습니다.
n := nums 배열의 크기로 설정하고, 맵 m을 정의하며, ret := 0으로 초기화한 뒤 nums의 각 원소 빈도를 m에 저장합니다.
cnt := 0으로 초기화합니다.
m의 각 쌍 it에 대해 다음을 반복합니다.
x := it의 키
temp := x × it의 값 (현재 숫자 × 빈도)
it1 := it의 이전 반복자, it2 := it1의 이전 반복자
cnt ≥ 1이고 x − it1의 키 > 1이면, temp := temp + m[it1의 키]
그렇지 않고 cnt ≥ 2이면, temp := temp + m[it2의 키]
a := cnt ≥ 1일 때 m[it1의 키], 그렇지 않으면 0
m[it의 키] := max(temp, a)
ret := max(ret, temp)
cnt를 1 증가시킵니다.
ret을 반환합니다.
여기서 핵심은 인접한 숫자, 즉 차이가 정확히 1인 숫자끼리는 동시에 선택할 수 없다는 점입니다. 따라서 현재 숫자와 이전 숫자의 차이가 1보다 크면 서로 충돌하지 않으므로 이전 위치까지의 최적해를 그대로 이어받고, 차이가 정확히 1이면 두 칸 앞의 최적해에 현재 점수를 더해 비교합니다.
예제(C++)
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int n = nums.size();
map <int, int> m;
int ret = 0;
for(int i = 0; i < nums.size(); i++){
m[nums[i]]++;
}
int cnt = 0;
map <int, int> :: iterator it = m.begin();
while(it != m.end()){
int x = it->first;
int temp = x * it->second;
map <int, int> :: iterator it1 = prev(it);
map <int, int> :: iterator it2 = prev(it1);
if(cnt >= 1 && x - it1->first > 1){
temp += m[it1->first];
}
else if(cnt >= 2){
temp += m[it2->first];
}
m[it->first] = max(temp, cnt >= 1 ? m[it1->first] : 0);
ret = max(ret, temp);
it++;
cnt++;
}
return ret;
}
};
main(){
vector<int> v = {3,4,2};
Solution ob;
cout << (ob.deleteAndEarn(v));
}
입력
[3,4,2]
출력
6
복잡도 분석
시간 복잡도는 맵에 원소를 삽입하고 순회하는 데 O(n log n)이 소요되며, 공간 복잡도는 배열에 등장하는 고유한 숫자의 개수에 비례해 O(n)입니다.