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

링크

https://school.programmers.co.kr/learn/courses/30/lessons/68644?language=java

프로그래머스

 

문제 요약

정수 배열 numbers에 대해 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 오름차순으로 정렬한다.

이때, 중복을 허용하지 않는다.

 

제한

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

 

풀이

numbers의 길이가 100 이하로, 작은 값이므로 시간 복잡도가 커도 상관없습니다.

1. numbers에서 만들 수 있는 두 개의 수 합을 모두 찾는다.
2. 이를 중복 제거한다.
3. 마지막으로 정렬한다.

 

코드

1. HashSet 사용하기

import java.util.*;

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

        return answer;
    }
}

 

[시간 복잡도]

• N: numbers 배열의 길이
• 이중 for문 → O(N^2)
  • set.add() → O(1)
• set의 최대 길이: N^2
• sorted() → O((N^2) log(N^2))
• 최종 시간 복잡도 = O(N^2)+O((N^2) log(N^2)) = O((N^2) log(N^2))

 

---

 

2. distinct() 사용하기

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<numbers.length-1; i++){
            for(int j=i+1; j<numbers.length; j++){
                list.add(numbers[i]+numbers[j]);
            }
        }
        int[] answer = list.stream().distinct().sorted().mapToInt(Integer::intValue).toArray();

        return answer;
    }
}

 

hashSet 사용하는 것과 달라진 점은 중복 제거를 위해 스트림화한 후, distinc() 함수를 사용해야 한다는 것입니다.