[프로그래머스/Lv.1] 두 개 뽑아서 더하기

문제 설명

정수 배열 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 해야 합니다.

 

 

⭕ 풀이

import java.util.*;

class Solution {
    public int[] solution(int[] arr) {
        int[] result = {};
        
        Set<Integer> set = new HashSet<Integer>();
        for(int i=0;i<arr.length-1;i++) { // 중복제거
            for(int j=i+1;j<arr.length;j++) {
                set.add(arr[i]+arr[j]);
            }
        }
        
        result = new int[set.size()];
        Iterator<Integer> ita = set.iterator();
        int k=0;
        while(ita.hasNext()) {            // 배열복사
            result[k] = ita.next();
            k++;
        }
        
        for(int i=1;i<result.length;i++) { // 삽입정렬
            for(int j=i;j>0;j--) {
                if(result[j]<result[j-1]) {
                    int temp = result[j];
                    result[j] = result[j-1];
                    result[j-1] = temp;
                }else {
                    break;
                }
            }
        }
        
        return result;
    }
}

 

우선 반환할 int[] result의 길이를 알 수 없기때문에

가변길이가 가능한 list,set,map 중 set을 사용해 풀이했다.

 

✅ Set의 특징

자료의 중복 저장이 허용되지않는다.

저장 순서가 유지되지 않는다.(인덱스가 없다)

이 중 중복값이 저장되지않는 특징을 사용하기위해 HashSet을 사용하였다.

 

for문에서 arr의 두 원소를 뽑아 더한 뒤 set에 담는다

arr[0]은 2이며 arr[1], arr[4] 둘다 값이 1이므로 [0]+[1] 과 [0]+[4]는 값이 3으로 값이 같다.

때문에 set에 add한다한들 중복값이므로 3이 두번저장되지않는다.

 

이렇게 중복이제거된 set의 길이만큼 result의 길이를 설정한다.

이후 Iterator를 사용하여 set의 각 값을 result에 옮겨담는다.

set의 특성상 인덱스가 없기때문에 list처럼 get(0) get(1) 이런식으로 사용이 불가능하다

따라서 set의 제어권을 Iterator에게 전달한 뒤 Iterator의 메서드를 사용해야한다.

 

이렇게 result에 옮겨담아진 값을 사용하기 편한 정렬방법으로 정렬해주면 된다.

위의 풀이에서는 삽입정렬을 사용하였다.

아직 퀵,합병 등의 정렬은 익숙치못해서 차츰 연습해보려고한다

 

 

 

import java.util.*;

class Solution {
    public Integer[] solution(int[] arr) {
        Integer[] result = {};
        
        Set<Integer> set = new HashSet<Integer>();
        for(int i=0;i<arr.length-1;i++) {
            for(int j=i+1;j<arr.length;j++) {
                set.add(arr[i]+arr[j]);
            }
        }
        
        result = new Integer[set.size()];
        set.toArray(result);
        Arrays.sort(result);
        
        return result;
    }
}

이런식으로 Collections 의 메서드 들을 사용하여 풀이하면 코드는 간결해지지만

속도도 경우에따라 좀 더 소요되기도하고 정렬 연습도 할겸 당분간은 최대한 Collentions의 메서드 없이 풀이해보려고한다.

 

 

 

 

-출처

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