프로그래머스[자바] - 두 개 뽑아서 더하기

---

2 + 1 = 1 +2이다. (2,1) = (1,2)이다. 즉, 조합을 찾는 문제이다. (numbers가 같은 숫자도 존재할 수 있으니 서로다른 n개중 r개를 뽑는 조합과는 완전히 같다고 할 순 없지만 같은 방식으로 접근..)

 

조합문제

1) dfs 탐색

2) 구현

 

둘 중에 무엇을 선택할지 결정해야하니, Input Size부터 확인해보자.

numbers의 최대길이는 100이므로 Worst Case: 100개 중 2개를 뽑는 경우 = 100C2 =  4950 ,, Input Size도 작고 탐색수도 많은 편이 아니니 dfs탐색으로 진행해도 무리가 없어보인다.

 

 

DFS 탐색

DFS 탐색을 하기 위해선 State Space Tree를 작성하는 것이 우선이다. (알고리즘의 흐름을 파악하기 위해)

SST 설계

visitArr [ i ] = 방문한 노드 라고 정의하자.

예를들어, (2, 1)인 경우 visitArr = [2, 1]

(2, 3)인 경우 visit = [2, 3] 인 것이다.

 

<Recursive Case>

매 재귀함수 호출마다 for문을 돌며 재귀적호출을 하며 방문을 할텐데 위의 SST를 참고하여 코드를 짜보면 다음과 같다.

dfs (int depth, int idx) {

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

      visitArr[depth] = numbers[i];

      dfs (depth+1, i+1);

   }

}

 

SST그림과 코드의 색깔을 매칭해보면 무슨말인지 알 것이다. 이러한 구조는 dfs로 조합을 구하는데 사용하는 전형적인 방식으로 익혀두자.

 

<Base Case>

1) DFS 재귀적 탐색이 언제 종료하는가?

SST를 보면 depth == 2일때 종료해야함을 알 수 있다.

 

2) 재귀턱 탐색이 종료할 때 무슨 작업을 해줘야하는가?

방문한 노드 visitArr을 모두 더해주고 그 결과를 HashSet에 넣어줘야한다. (중복X이므로 HashSet 사용)

코드는 다음과 같다.

dfs (int depth, int idx) {
//base case
        if (depth == 2) {
            result.add(visitArr[0]+visitArr[1]);
            // System.out.print("(" + visitArr[0] + "," +visitArr[1] +") ");
            return;
        }
}

 

 

dfs탐색을 종료했으면 문제조건인 오름차순으로 정렬해줘야 한다.

하지만, HashSet은 Unorderd Collection (데이터 위치적 순서의 전후관계가 없음) 이므로 정렬이 불가하다. 따라서, 우린 HashSet 와 동일한 엘레멘트를 갖는 List(Ordered Collection)를 만들어줘야 한다.

 

* LinkedList 생성자

LinkedList ( Collection c ) 즉, Collection 타입의 컨테이너를 파라미터로하여 List를 생성할 수 있으므로,

HashSet<Integer> result = new HashSet<>();
List<Integer> linkedList = new LinkedList<>(result);

 

이제, List를 정렬해보자.

*List정렬은 두가지 방법이 있다.

1) Collections 클래스의 sort( )

2) Arrays 클래스의 sort( )

 

1번이 빠르므로 되도록 1번을 쓰자. (Worst Case 1번: O(Nlgn), 2번: O(N^2))

(이정도 데이터크기는 별로 의미없긴할 것 같다)

Collections.sort(linkedList);

 

 

---

코드

import java.util.*;
class Solution {
    static int[] visitArr = new int[2];
    static int[] numbers;
    static HashSet<Integer> result = new HashSet<>();
    public int[] solution(int[] numbers) {
        this.numbers = numbers;
        int[] result2 = {};
        dfs(0,0);
        // System.out.println(result);
        List<Integer> linkedList = new LinkedList<>(result);
        Collections.sort(linkedList);
        int[] answer = new int[result.size()];
        for (int i=0; i<result.size(); i++) {
            answer[i] = linkedList.get(i);
        }
        return answer;
        
    }
    
    static void dfs(int depth, int idx) {
        //base case
        if (depth == 2) {
            result.add(visitArr[0]+visitArr[1]);
            // System.out.print("(" + visitArr[0] + "," +visitArr[1] +") ");
            return;
        }
        
        //recursive case
        for (int i=idx; i<numbers.length; i++) {
            
            visitArr[depth] = numbers[i];
            dfs(depth+1, i+1);
        }        
        
    }

}

 

---

기억하자!

1. dfs방식의 조합구하기

2. HashSet은 중복X,

Unordered Collection이므로 정렬X

(정렬하고싶으면 linkedList (Collection c) 생성자를 사용해 list로 만들고 Collections.sort( )로 정렬)