[프로그래머스] 두 개 뽑아서 더하기 - 리팩토링O

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

프로그래머스

 

0️⃣

문제

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

 

입력

 

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

 

1️⃣ 어떻게 문제를 풀까?

두 데이터의 합이 중복이 될 수 있으니까 Set을 써야겠다!

 

1) 첫번째 시도

import java.util.*;

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

무난하게 성공! but 속도가 아쉽다.. Set을 int[]로 바꾸는 연산에서 시간이 걸리는 것 같은데 다른 방법을 시도해보자!

 

2)두번째 시도

class Solution {
    public int[] solution(int[] numbers) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int i = 0; i < numbers.length; ++i)
            for(int j = i + 1; j < numbers.length; ++j)
                set.add(numbers[i] + numbers[j]);
        
        int[] answer = new int[set.size()];
        int i = 0;
        for(int num: set) answer[i++] = num;
        Arrays.sort(answer);
        
        return answer;
    }
}

❕.stream().mapToInt(i -> i).toArray(); 보다 단순히 for문으로 set → int[] 해주는게 성능이 더 좋다!

 

3) 구글링 좀 해보다가 발견한 풀이 (ArrayList 사용!)

class Solution {
    public int[] solution(int[] numbers) {
        ArrayList<Integer> arr = new ArrayList<>();
        
        for(int i = 0; i < numbers.length; ++i) {
            for(int j = i + 1; j < numbers.length; ++j) {
                int sum = numbers[i] + numbers[j];
                if(arr.indexOf(sum) < 0) arr.add(sum);
            }
        }
                
        arr.sort((a, b) -> a - b);
        
        int[] answer = new int[arr.size()];
        for(int i = 0; i < arr.size(); ++i) answer[i] = arr.get(i);
        
        return answer;
    }
}

❗ 중복값이 없음 = Set이였는데, 이런식으로 중복값을 제거할수도 있다는걸 알게됨!

 

🛠️ 리팩토링

: number의 최댓값이 100이므로 두 수의 합으로 나올 수 있는 최댓값은 200! 크기가 200인 check배열을 만들어서 두 수의 합을 index로 true를 세팅해주기! (동적 프로그래밍처럼!)

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        boolean[] check = new boolean[200];
        int count = 0;
        for(int i = 0; i < numbers.length; ++i) {
            for(int j = i + 1; j < numbers.length; ++j) {
                int sum = numbers[i] + numbers[j];
                if(!check[sum]) {
                    check[sum] = true;
                    count++;
                }
            }
        }
        
        int[] answer = new int[count];
        int index = 0;
        for(int i = 0; i < 200; ++i) 
            if(check[i]) answer[index++] = i;
        
        return answer;
    }
}