프로그래머스: Lv1. 두 개 뽑아서 더하기

• 문제 설명
  
  -정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.
  
  
• 제한사항
  
  - numbers의 길이는 2 이상 100 이하입니다.
  - numbers의 모든 수는 0 이상 100 이하입니다.
  
  
• 입출력 예

numbers	result
[2,1,3,4,1]	[2,3,4,5,6,7]
[5,0,2,7]	[2,5,7,9,12]

-입출력 예 설명 #1

• 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.)
• 3 = 2 + 1 입니다.
• 4 = 1 + 3 입니다.
• 5 = 1 + 4 = 2 + 3 입니다.
• 6 = 2 + 4 입니다.
• 7 = 3 + 4 입니다.
• 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

-입출력 예 설명 #2

• 2 = 0 + 2 입니다.
• 5 = 5 + 0 입니다.
• 7 = 0 + 7 = 5 + 2 입니다.
• 9 = 2 + 7 입니다.
• 12 = 5 + 7 입니다.
• 따라서 [2,5,7,9,12] 를 return 해야 합니다.

---

★ 나의 문제풀이

public int[] solution(int[] numbers) {
		Arrays.sort(numbers);
		List<Integer> tmpList = new ArrayList<>();
		List<Integer> sumList = new ArrayList<>();

//      배열의 중복을 제거하고 중복된값은 합배열에 추가해주는 방법.
		tmpList.add(numbers[0]);
		for (int i = 0; i < numbers.length - 1; i++) {
			if (numbers[i] != numbers[i + 1]) {
				tmpList.add(numbers[i + 1]);

			} else {
				if (!sumList.contains(numbers[i] * 2)) {
					sumList.add(numbers[i] * 2);
				}
			}
		}
		
        //중복이 제거된 tmpList를 활용하여 더한값을 sumList에 넣어주는 방법.
		for (int i = 0; i < tmpList.size() - 1; i++) {
			for (int j = i + 1; j < tmpList.size(); j++) {
				int sum = tmpList.get(i) + tmpList.get(j);
				if (!sumList.contains(sum)) {
					sumList.add(sum);
				}
			}
		}
		
		Collections.sort(sumList);
		int[] answer = new int[sumList.size()];
		int k = 0;
		for (int tmp : sumList) {
			answer[k++] = tmp;
		}
		return answer;
	}

• 배열요소를 인덱스 n과 n+1로 비교를 한다.
• 그러기 위해서 먼저 오름차순으로 배열을 정렬한다. 
  
  -정렬하려는 이유는 배열의 같은 값을 갖는 요소들을 붙어놓으려고 생각했다. 인덱스를 1증가시키며 비교할 때 중복인 숫자를 빼내기 쉬울것으로 예상했다.
  
  -ex) [2,1,3,4,1] -> [1,1,2,3,4]
• tmpList라는 ArrayList 첫번째 요소에 정렬된 배열의 요소를 넣어준다. 
  
  - 인덱스 n과 n+1 이 0과 1일때 첫번째 요소부터 같으면 numbers[0]값을 사용해야 하기 때문.
  
  - tmpList.add(numbers[0]);
• 비교해서 두 수가 같지 않으면 뒤에 수를 중복제거용list인 tmpList에 삽입한다.
• 비교해서 두 수가 같으면 앞에 수를 곱하기 2하여 합 list인 sumList에 삽입한다.
  
  -합 리스트 안에 더한값의 중복이 있을수 있으므로 중복 확인을 한다. contains()사용.
• 비교과 완료되고 중복을 제거한 요소값은 tmpList에 오름차순으로 들어가게 된다.
• 비교과 완료되고 중복된 요소값은 더하기까지 완료되어 sumList에 들어간다.
• 이제 tmpList에 있는 요소들을 처음부터 두개씩 뽑아 나가며 sumList에 보낼것이다.
• 이중 for문을 사용하여 더해나가고 sumList의 중복요소 확인을 위하여 contains()함수를 사용한다.
• sumList에 추가를 완료하면 애초에 들어가있었던 값 뒤에 더해지기 때문에 정렬을 다시한번 해준다.
• 완료된 sumList를 정답배열에 순차적으로 삽입하면 완료된다.

- 다른풀이와 차이점.

• 애초에 요소가 담긴 문제배열에 중복값이 많아졌을때를 생각하여, 중복값과 중복이 되지않은 값을 두 ArrayList 에 따로 담는 방법을 생각하였다. 
• 큰 과정으로 보면 
  1. 문제배열을 정렬한다.
  2. 그 배열을 둘로 나눠서 리스트에 저장한다.
  3. 각각의 리스트를 구현한다.
  4. 다시 두 리스트를 모아 정답배열에 합친다.
• 위 과정을 보면 너무나 길어지기 마련이고, 중복제거를 위해서 쓰는 반복문과 조건문도 상당하여 효율성이 되려 떨어지는 느낌이다.
• 그러나 다른문제풀이를 본 후 컬렉션에 set을 이용하면 중복을 허용하지 않는다는 것을 알게되었다.
• 심지어 set에 treeset 이라는 방법을 쓰면 중복이 허용되지 않고, 오름차순으로 정렬시켜준다.

★다른 문제 풀이

  -TreeSet을 이용한 풀이 (그냥 Set을 이용하려면 sort를 필수로 해주어야 한다.!)

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

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

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

        int[] answer = new int[sumNumber.size()];
        int index = 0;
        Iterator itor = sumNumber.iterator();
        while(itor.hasNext()){
            answer[index] = (int)itor.next();
            index++;
        }

        return answer;
    }
}