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

 

문제 

설명

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

제한사항

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

 

 

풀이 

풀이 1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;



class Solution {
    public int[] solution(int[] numbers) {
        ArrayList<Integer> result = 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(!result.contains(sum)) result.add(sum);
            }
        }
    
        Collections.sort(result);
        int[] arr = new int[result.size()];
        for(int i = 0; i < result.size(); i++){
            arr[i] = result.get(i);
        }
        
        return arr;
    }
}

요약 

- ArrayList를 활용해서 ArrayList의 contains를 이용해서 중복 숫자 배제

- for문에서 j=i+1 부터 시작하여 자기자신끼리 더하는 경우 없도록 함

- Collections.sort를 활용해 오름차순 정렬 후 ArrayList를 배열로 변환 후 return. 

시간 복잡도 분석

n = numbers의 크기, k = result의 크기

 

1) for문 외부 내부 루프 n*(n-1) : O( n² -n)

2) ArrayList.contains() 연산  : O(n) 

3) add() 연산 : O(1)

--- 이 부분 시간 복잡도 : O(n³) 

 

4) Collections.sort() : O(k log k)

5) 배열로 변환하는 부분 : O(k) 

최종 시간 복잡도 : O(n³) + O(k log k) = O(n³)

 

 

 

풀이 2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;


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++){
                int sum  = numbers[i] + numbers[j];
                set.add(sum);
            }
        }
    
        
        return set.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
}

요약 

- HashSet을 사용하여 요소 추가 시 중복 배제

- return 시, HashSet을 스트림으로 변환 -> sorted()로 스트림 요소들을 오름차순 정렬 -> mapToInt로 Stream<Integer>를 IntStream으로 변환. Integer::intValue 로 Integer 객체를 기본형 int로 변환 ( x -> x.intValue()) -> toArray()를 통해 intStream을 int[] 배열로 변환

시간 복잡도 분석

n = numbers의 크기, k = result의 크기

1) for문 외부 내부 루프 n*(n-1) : O( n² -n)

3) Hashset add() 연산 : O(1)

-- 이 부분 시간 복잡도 : n²

 

4) stream 생성 : O(1)

5) sorted(): O(k log k)

6) mapToInt(): O(k)

7) toArray(): O(k)

-- 최종 시간 복잡도 : O(n²) + O(k log k) = O(n²)

 

 

 

정리

풀이 1( n³ )보다 풀이 2( n² )가 시간복잡도로 봤을 때 더 효율적이다.