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

1. 문제

---

 

 

2. 풀이 과정

---

• 배열에서 두 개씩 뽑아 더 한다.
• 이 문제에서 함정은 중복이다. 
  • 두 수를 더한 결과가 중복되면 결과 배열에 포함되면 안된다. 
  • ex) [5, 0, 2, 7]  → (5 + 2) = 7, (0 + 7) = 7  
    • --> 7은 한번만 저장되어야 함
• 이후 오름차순으로 정렬 

 

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = {};
        ArrayList<Integer> temp = new ArrayList<>();
        
        for(int i = 0; i < numbers.length - 1; i++) {
            for(int j = i + 1; j < numbers.length; j++) {
                int sum = numbers[i] + numbers[j]; // 배열의 값 들을 두 개씩 더함
                
                if(temp.size() == 0) { // 리스트가 비어있을 때
                    temp.add(sum);
                }
                for(int k = 0; k < temp.size(); k++) {
                    if(sum == temp.get(k)) { // 중복 체크
                        break;
                    }
                    
                    if(k == temp.size() - 1) { // 중복되지 않는다면 리스트에 추가
                       temp.add(sum);
                    }
                }
            }
        }
        Collections.sort(temp); // 리스트 오름차순으로 정렬
        
        answer = new int[temp.size()]; // 결과 배열의 크기를 리스트의 크기만큼 할당
        
        for(int i = 0; i < answer.length; i++) { // 리스트의 값을 결과 배열로 옮기기
            answer[i] = temp.get(i);
        }
        
        
        return answer;
    }
}

 

시간 복잡도

• O(N^4)

• temp 리스트의 최대 크기는 배열에서 두 개의 수를 뽑는 경우인 n(n-1) / 2이기 때문에 시간복잡도는                          총 O(N^4)가 나온다.
• numbers의 최대 길이가 100이라 정답처리는 됐지만 상당히 비효율적인 코드가 나와버렸다. 

 

4. 다른 정답 코드와 비교

---

프로그래머스 최다 좋아요 코드

import java.util.HashSet;
import java.util.Set;

class Solution {
     public int[] solution(int[] numbers) {
        Set<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]);
            }
        }

        return set.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

시간복잡도

• O(N^2 logN)
  • Set 컬렉션을 사용해서 중복처리하는 부분을 해결해서 두 수의 합을 처리하는 부분이 O(N^2)으로 줄었다.
  • 이후 정렬하는 부분이 O(N^2 logN)이라서 최종적인 시간복잡도가 O(N^2 logN)이 나왔다.

 

TreeSet을 활용한 코드

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        TreeSet<Integer> set = new TreeSet<>(); // 중복체크와 오름차순 정렬을 위한 TreeSet
        
        for(int i = 0; i < numbers.length - 1; i++) {
            for(int j = i + 1; j < numbers.length; j++) {
                set.add(numbers[i] + numbers[j]);
            }
        }
        
        return set.stream().mapToInt(Integer::intValue).toArray();
    }
}

• TreeSet은 중복처리와 동시에 정렬까지 해주는 컬렉션이다.
• 시간복잡도는 똑같이 O(N^2 logN)이다. 

 

5. 피드백

---

• 중복 체크를 해야한다면 무조건 Set을 사용하는 것이 좋다. 
  • for문을 돌려 중복체크를 한다면 O(N)이상의 시간복잡도가 발생하는데 Set컬렉션을 사용하면 O(1)로
    중복을 체크할 수 있다.
• 중복체크에 정렬기능까지 필요하다면 TreeSet을 사용하는 것도 좋다.