[프로그래머스] 두 개 뽑아서 더하기(java)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/68644

프로그래머스

---

나의 풀이

import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

class Solution {
    private static Set<Integer> set = new TreeSet<>();

    public int[] solution(int[] numbers) {

        boolean[] visited = new boolean[numbers.length];
        comb(numbers, visited, 0, numbers.length, 2);

        int[] answer = new int[set.size()];
        int i = 0;
        Iterator iter = set.iterator();
        while (iter.hasNext()) {
            answer[i] = (int) iter.next();
            i++;
        }

        return answer;
    }

    private void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            sumSet(arr, visited, n);
            return;
        }

        if (depth == n) {
            return;
        }

        visited[depth] = true;
        comb(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        comb(arr, visited, depth + 1, n, r);
    }

    static void sumSet(int[] arr, boolean[] visited, int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                sum += arr[i];
            }
        }
        set.add(sum);
    }
}

배열에서 두 개의 수를 더하여 나올 수 있는 모든 경우의 수를 구하라고 했을 때, 조합 알고리즘이 떠올랐다.

 

이전에 포스팅 한 조합 알고리즘 코드를 응용해서 문제를 풀었고, 더한 값 결과들이 오름차순 정렬이라서 TreeSet을 사용하였다. 

 

Set, List 등 Collections에서 int형 배열로 stream()을 사용하여 변경하는 걸로 구현했는데 속도면에서 너무 안좋아서 Iterator를 사용하여 배열에 값을 삽입하는 형식으로 구현하였다. 

 

속도는 거의 5배 차이 났음.

 

또다른 방식으로 2중 for문과, stream() 을 사용하여 코드를 간단하게 작성해보았다.

import java.util.TreeSet;
import java.util.Set;

class Solution {
     public int[] solution(int[] numbers) {
        Set<Integer> set = new TreeSet<>();

        for(int i=0; i<numbers.length; i++) {
            for(int j=i+1; j<numbers.length; j++) {
                set.add(numbers[i] + numbers[j]);
            }
        }

        return set.stream().mapToInt(Integer::intValue).toArray();
    }
}