엘리스 코드 챌린지 Day 5 수열 복원

문제

 

풀이

이 문제는 방법이 다양한것 같았습니다. dfs로 푸신분들도 계셨지만 저는 최근에 그리디를 좀 많이 풀었어서 그런지 그리디로 먼저 접근했습니다.

 

우선 수열이 a1, a2, a3, ... an 까지 존재한다고 했을 때 이 수열의 부분수열의 합을 2^n개 만들 수 있습니다.

하지만 문제에서 주어지는 입력은 그 부분수열의 합인 2^n개의 수가 주어집니다.

따라서 어떤 수열의 조합으로 입력되는 부분 수열의 합을 만들 수 있는지 원래 수열의 원소들을 구하는 문제입니다.

 

처음 생각해본건 두가지입니다.

1. 입력으로 주어지는 수열 중 0은 절대 답이 될 수 없음

2. 0 다음으로 제일 작은 수는 무조건 원래 수열의 원소에 해당함

1번은 원래 수열의 원소 ai의 범위는 1 ~ 100000입니다. 0을 만들려면 어떤 원소도 더하지 않는 경우밖에 없습니다.

2번은 0 다음으로 제일 작은 수는 어떤 수를 더하더라도 만들 수 없습니다. 그냥 자신만이 그 수를 만들 수 있습니다.

0 다음으로 제일 작은 수가 여러개라면 그 같은 수들을 모두 더해주도록 합니다.

 

여기서 시작해서 어떻게 그리디하게 접근할 수 있을까 고민하다가 map과 set을 사용하게 되었습니다.

map과 set에는 원래 수열로 인해 제거되는 부분 수열의 값을 저장합니다.

제가 수를 제거한 방식으로는

set에 지금까지 모은 원래 수열의 부분 수열의 합을 모두 다 저장합니다.

map에는 set에서 구한 합들을 카운팅합니다.

 

예를들어 지금까지 구한 원래 수열이 1, 2, 3라고 했을 때 얘내들의 부분 수열의 합은 0 1 2 3 3 4 5 6 입니다.

그리고 다음 추가되는 원소가 4라고 했을 때 원래 수열은 1, 2, 3, 4가 되고,

이전에서 구했던 부분 수열의 합에서 모두 +4를 해주면 4 5 6 7 7 8 9 10이 되는데,

이걸 부분 수열의 합으로 모두 추가하면 0 1 2 3 3 4 4 5 5 6 6 7 7 8 9 10이 되고, 이는 수열 1, 2, 3, 4의 부분 수열의 합이 됩니다.

 

위에서 구한 값들을 set과 map에 넣어주고,

다음 들어오는 값을 key로 map에 검색하여 1 이상으로 카운팅되어 있다면 선택하지 않고 넘어가는 방식입니다. 이때 map[key]를 1씩 감소시킵니다.

여기서 map을 사용한 이유는 원래 수열의 원소를 원래 수열의 합으로 만들 수도 있기 때문입니다.

2 4 6이 원래 수열이라면 2 + 4로도 6을 만들 수 있기 때문에 6이 걸러지는 문제가 있었습니다. 덕분에 코드가 더러워졌습니다...

map에서 카운팅한 만큼의 수를 걸러내고, 제거되지 않은 수들 중 제일 작은 수를 순서대로 넣어주면 원래 수열을 구할 수 있습니다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define MAX 1500001
using namespace std;
 
set<int> s;
map<int, int> m;
vector<int> v;
int list[MAX];
int N;
 
void eraseNum(int x) {
    set<int>::iterator iter = s.begin();
    vector<int> tmp;
    for (; iter != s.end(); iter++) {
        tmp.push_back(*iter + x);
    }
 
    for (auto y : tmp) {
        m[y]++;
        s.insert(y);
    }
}
 
void init() {
    sort(list, list + (1 << N));
 
    v.push_back(list[1]);
    m[0]++;
    m[list[1]]++;
    s.insert(0);
    s.insert(list[1]);
    for (int i = 2; i < (1 << N); i++) {
        if (list[1] != list[i]) break;
 
        v.push_back(list[i]);
        eraseNum(list[i]);
    }
}
 
void func() {
    init();
    for (int i = 2; i < (1 << N); i++) {
        if (m.find(list[i]) != m.end()) {
            m[list[i]]--;
            if (!m[list[i]]) m.erase(list[i]);
            continue;
        }
        if (v.size() == N) break;
 
        v.push_back(list[i]);
        eraseNum(list[i]);
        for (int j = i + 1; j < (1 << N); j++) {
            if (list[i] != list[j]) break;
            if (v.size() == N) break;
            v.push_back(list[j]);
            eraseNum(list[j]);
        }
    }
 
    for (auto x : v) {
        cout << x << ' ';
    }
    cout << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < (1 << N); i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}