[프로그래머스] 프로그래머스 Level1 두 개 뽑아서 더하기 Java

문제

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

코딩테스트 연습 - 두 개 뽑아서 더하기

풀이

백트래킹을 통해서 문제를 해결할 수 있었다.

nCr 조합이라 가정할때 n은 numbers 배열의 인덱스 기반으로 2개를 뽑으면 돼서 numbers의 크기가 될 것이고 r은 2개를 뽑아서 더하는 것이니까 2가 될 것이다. n과 r이 무엇인지 알았으니 조합을 돌려주면 되고, 조합의 합산 결과들의 중복을 방지하기위해 각각 set에 저장해주었다. set에 저장해준 후에는 다시 배열로 옮겨주었고 정렬 후에 답을 리턴해주면 된다.

코드

import java.util.*;

// 프로그래머스
class 두 개 뽑아서 더하기 {

    public int[] arr = new int[101];
    public boolean[] isused = new boolean[101];
    public HashSet<Integer> set = new HashSet<>();

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

        // combination
        func(0, 0, numbers);

        // set -> Array
        int[] answer = new int[set.size()];
        Iterator<Integer> iter = set.iterator();
        int index = 0;
        while (iter.hasNext()) {
            answer[index] = iter.next();
            index++;
        }

        Arrays.sort(answer);

        return answer;
    }

    void func(int idx, int cnt, int[] numbers) {
        if(cnt == 2) {
            int tmp = 0;
            for(int i = 0; i < 2; i++) {
                tmp += numbers[arr[i]];
            }
            set.add(tmp);
            return;
        }

        for(int i = idx; i < numbers.length; i++) {

            if(!isused[i]) {
                isused[i] = true;
                arr[cnt] = i;
                func(idx + 1, cnt + 1, numbers);
                isused[i] = false;
            }
        }
    }
}