[엘리스 알고리즘 코드 챌린지] Day 5. 수열 복원 (Java)

문제

---

핵심

핵심 로직

단순한 방법으로는 모든 부분 수열의 합 조합을 제거하는 것이다.

수열이 [1, 2, 4] 인 경우를 생각하면

모든 부분 수열의 합은 아래와 같다.

0

a1

a2

a3

a1 + a2

a1 + a3

a2 + a3

a1 + a2 + a3

 

a1, a2, a3는 원래의 수열이고 그 외의 것들은 a1, a2, a3를 조합하여 합한 것임을 알 수 있다.

따라서 주어진 부분 수열의 합을 정렬하고 작은 수부터 짝지어 합한 후 제외하면 결과적으로 원래의 수열이 남게 된다.

 

예를 들어 [0 1 2 3 4 5 6 7] 이 주어졌다면,
일단 공집합 0을 제외하고

1 + 2 = 3 제거 [1 2 3 4 5 6 7]
1 + 4 = 5 제거 [1 2 3 4 5 6 7]

1 + 6 = 7 제거 [1 2 3 4 5 6 7]

2 + 4 = 6 제거 [1 2 3 4 5 6 7]

=> [1, 2, 4]

 

시간복잡도

핵심 로직은 위와 같이 간단하지만 구현에 신경을 쓸 점이 조금 있다.

두 수를 선택해서 일일이 합하는 방법은 시간복잡도가 O(N^2)이다.

N이 최대 2^15(32768)이므로 시간초과가 날 수 있다.

 

중복 처리

입력이 아래와 같이 주어진 경우, 원래의 수열이 [1, 1]이다. 즉, 중복된 원소를 고려해야 한다.

2
0 1 1 2

---

구현 1

시간 복잡도를 줄이기 위해 해시 자료구조를 사용해야겠다는 생각을 했고,

그 중에서 가장 작은 값을 쉽게 얻을 수 있는 TreeMap을 사용하였다.

처음에는 시간복잡도를 줄이기 위해 TreeSet을 사용했는데, 중복된 원소의 개수를 값에 포함하기 위해서 TreeMap으로 바꾸었다.

---

Code (Java) with TreeMap

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int m = (int) Math.pow(2, n);
        int[] sums = new int[m];

        StringTokenizer st = new StringTokenizer(br.readLine());
      
        for (int i = 0; i < m; i++) {
            sums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(sums);

        List<Integer> originalSequence = findOriginalSequence(sums, n);
        
        for (int num : originalSequence) {
                sb.append(num).append(' ');
        }
        System.out.println(sb.toString().trim());
    }

    private static List<Integer> findOriginalSequence(int[] sums, int n) {

        List<Integer> originalSequence = new ArrayList<>();
        Multiset multiset = new Multiset();

        for (int sum : sums) {
            multiset.add(sum);
        }

        multiset.remove(0);
        List<Integer> sumList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int smallest = multiset.pollFirst();
            
            List<Integer> newSums = new ArrayList<>();
            for (int elem : sumList) {
                newSums.add(elem + smallest);
            }
            
            for (int sum : newSums) {
                multiset.remove(sum);
                sumList.add(sum);
            }
            sumList.add(smallest);
            originalSequence.add(smallest);
        }
        return originalSequence;
    }
}

class Multiset {
    private final TreeMap<Integer, Integer> map = new TreeMap<>();

    public void add(int value) {
        map.put(value, map.getOrDefault(value, 0) + 1);
    }

    public void remove(int value) {
        if (map.containsKey(value)) {
            if (map.get(value) == 1) {
                map.remove(value);
            } else {
                map.put(value, map.get(value) - 1);
            }
        }
    }

    public int pollFirst() {
        Map.Entry<Integer, Integer> entry = map.firstEntry();
        int value = entry.getKey();
        remove(value);
        return value;
    }
}

---

구현 2

DFS를 활용한 방법

포함된 인강이 힌트라고 들었는데 이번에도 그랬고 이 방법이 구현하기 훨씬 간단한 것 같다.

원리는 이전과 똑같다.

---

Code (Java) with DFS

코드 출처: 생쥐

import java.io.*;
import java.util.*;

class Main {
    public static int[] nums;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        
        nums = new int[(int)Math.pow(2, N)];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < Math.pow(2, N); i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);

        dfs (0, 1, 0);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                sb.append(nums[i]).append(" ");
            }
        }

        System.out.println(sb);
    }

    public static void dfs (int cnt, int start, int sum) {
        if (cnt == 2) {

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == sum) {
                    nums[i] = 0;
                    break;
                }
            }

            return;
        }

        for (int i = start; i < nums.length; i++) {
            if (nums[i] != 0) {
                dfs (cnt + 1, i + 1, sum + nums[i]);
            }
        }
    }
}