두 개 뽑아서 더하기

문제 설명

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

풀이

public class SumCombinator
{
    public static int[] Solution(int[] numbers)
    {
        List<int> sums = new List<int>();
        for (int i = 0; i < numbers.Length; i++)
        {
            for (int j = i + 1; j < numbers.Length; j++)
            {
                int sum = numbers[i] + numbers[j];
                
                if(!sums.Contains(sum))
                    sums.Add(sum);
            }
        }
        
        sums.Sort();
        
        return sums.ToArray();
    }
    
    public static int[] Solution2(int[] numbers)
    {
        HashSet<int> sums = new HashSet<int>();
        
        for (int i = 0; i < numbers.Length; i++)
        {
            for (int j = i + 1; j < numbers.Length; j++)
            {
                int sum = numbers[i] + numbers[j];
                
                sums.Add(sum);
            }
        }
        
        List<int> result = sums.ToList();
        result.Sort();
        
        return result.ToArray();
    }
}

List를 사용한 방법

    public static int[] Solution(int[] numbers)
    {
        List<int> sums = new List<int>();
        for (int i = 0; i < numbers.Length; i++)
        {
            for (int j = i + 1; j < numbers.Length; j++)
            {
                int sum = numbers[i] + numbers[j];
                
                if(!sums.Contains(sum))
                    sums.Add(sum);
            }
        }
        
        sums.Sort();
        
        return sums.ToArray();
    }

• List를 사용해 모든 합을 더해 최종적으로 정렬한 배열을 반환
• Contains을 통해 여러 합 중에서 겹치는 값이 없도록 함

HashSet을 사용한 방법

    public static int[] Solution2(int[] numbers)
    {
        HashSet<int> sums = new HashSet<int>();
        
        for (int i = 0; i < numbers.Length; i++)
        {
            for (int j = i + 1; j < numbers.Length; j++)
            {
                int sum = numbers[i] + numbers[j];
                
                sums.Add(sum);
            }
        }
        
        List<int> result = sums.ToList();
        result.Sort();
        
        return result.ToArray();
    }

• 앞선 List를 사용한 방법에서는 주어진 수가 많아질 경우 Contains를 통해 고유한 값인지 확인하고자 할 때 O(N)의 시간복잡도가 발생해 병목 현상이 발생할 수 있음
• 이를 개선하기 위해 단일 값만을 남기는 HashSet을 사용해 해당 시간 복잡도를 평균 O(1)로 개선