두 개 뽑아서 더하기

문제정의

---

정수 배열 numbers가 주어질 때 서로 다른 인덱스에 있는 두 개의 숫자를 뽑아 더해서 만들 수 있는 모든 경우의 수를 배열로 담아 반환하는 문제이다.

문제풀이

---

간단한 문제이다. 두 수를 모두 더해보면서 배열에 넣으면 된다. 다만, 중복인 배열이 있으면 안되므로 set를 활용한다.

전체 코드는 다음과 같다.

import java.util.*;

public class PickTwoSum {

    public static void main(String[] args)
    {
        int[] numbers = {2, 1, 3, 4, 1};

        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < numbers.length; i++)
        {
            for(int j = i+1; j < numbers.length; j++)
            {
                set.add(numbers[i]+numbers[j]);
            }
        }
        
        List<Integer> list = new ArrayList<>(set);
        list.sort(null);
        Integer arr[] = new Integer[list.size()];
        arr = list.toArray(arr);
        int[] answer = new int[arr.length];
        for(int i = 0; i < arr.length; i++)
        {
            answer[i] = Integer.parseInt(arr[i].toString());
        }

        

    }
    
}

부분부분 살펴보자

HashSet<Integer> set = new HashSet<Integer>();
for(int i = 0; i < numbers.length; i++)
{
    for(int j = i+1; j < numbers.length; j++)
    {
        set.add(numbers[i]+numbers[j]);
    }
}

중복을 방지하기 위해 배열이 아닌 set을 선언한다. 두 수를 더해서 set에 더해간다. set에 add를 하는 것은 \(O(1)\)이다. 따라서 for문에 의해 이부분은 \(O(n^2)\)이다.

List<Integer> list = new ArrayList<>(set);
list.sort(null);
Integer arr[] = new Integer[list.size()];
arr = list.toArray(arr);
int[] answer = new int[arr.length];
for(int i = 0; i < arr.length; i++)
{
    answer[i] = Integer.parseInt(arr[i].toString());
}

set은 순서에 상관하지 않기 때문에 정렬이라는 개념이 없다. 그래서 이를 list로 바꿔준뒤 int형태로 바꿔주는 과정이다. list에 있는 sort는 \(O(nlogn)\)이고 for문은 \(O(n)\)이므로 이 부분에서 시간복잡도는 \(O(nlogn)\)이다.

따라서 총 걸리는 시간 복잡도는 \(O(n^2)\)이다.

테스트

pick_two_sum_result

c++로 코딩을 하다가 다시 자바를 하려니 까먹은 자료구조나 메소드가 많다. 앞으로 천천히 익혀나가야겠다.