[Lv.1] 두 개 뽑아서 더하기 [프로그래머스_코딩테스트] [Set, 정렬] [25분]

🔍 문제 요약

https://school.programmers.co.kr/learn/courses/30/lessons/68644

프로그래머스

정수 배열 numbers에서 숫자 2개를 뽑아서 더한 값을 중복이 없이 해서 오름차순 정렬하기

🧠 나의 접근 방식과 시행착오

약 16분 정도 걸린 문제. 문제는 빠르게 풀었지만 최적화 그런 부분 고려하지 않고 시간 절약형으로 단순하게 푼 듯 하다. 2중 for문을 돌면서 숫자 두개의 합을 더한 값을 List에 없으면 넣고 Sort를 돌려버리는 것 뿐

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 두 개 뽑아서 더하기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/68644
    /// </summary>
    public int[] solution(int[] numbers)
    {
        List<int> sumList = new List<int>();

        for (int i = 0; i < numbers.Length - 1; i++)
        {
            for (int j = i + 1; j < numbers.Length; j++)
            {
                int pick1 = numbers[i];
                int pick2 = numbers[j];
                int sum = pick1 + pick2;

                if (!sumList.Contains(sum))
                {
                    sumList.Add(sum);
                }
            }
        }

        sumList.Sort();
        return sumList.ToArray();
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var numbers1 = new[] { 2, 1, 3, 4, 1 };
        var numbers2 = new[] { 5, 0, 2, 7 };
        var res1 = sl.solution(numbers1);
        var res2 = sl.solution(numbers2);

        foreach (var item in res1)
        {
            Console.Write($"{item}, ");
        }
        
        Console.WriteLine();
        
        foreach (var item in res2)
        {
            Console.Write($"{item}, ");
        }
    }
}

✅ 풀이 코드

문제의 풀이 자체는 틀리지 않았다. 다만 시간 효율이 좋지 못하다는 점에 더 효율적인 코드를 피드백으로 받았다. 필자가 푼 문제에서 List의 Contains는 사실상 O(N)의 반복을 돌리는거라 3중 for문이 돈다고 볼 수 있어서 매우 효율면에 좋지 않음. 그렇기에 이 문제에서는 중복을 막는 부분이 중요한데, 그 때 사용하는 것이 HashSet이다. 자동으로 Add를 했을 때 중복된 것은 거르기 때문에 일다 넣으면 된다. 추가로 마지막에 정렬의 경우 HashSet 자체에 정렬 기능이 존재하지 않아 List에 넣어서 Sort를 돌려야 한다. 그 외에 Linq로 OrderBy 같은 것을 쓸 수도 있지만 C# 8이상이라고 함.

public int[] solution(int[] numbers)
{
    HashSet<int> sums = new HashSet<int>();

    for (int i = 0; i < numbers.Length - 1; i++)
    {
        for (int j = i + 1; j < numbers.Length; j++)
        {
            int sum = numbers[i] + numbers[j];
            sums.Add(sum); // HashSet은 자동으로 중복 제거
        }
    }

    // HashSet → List로 변환 후 정렬
    var result = new List<int>(sums);
    result.Sort();

    return result.ToArray();
}

🔄 정리

중복을 거르는 경우 HashSet을 기억해 두면 유용하게 효율을 높일 수 있는 것을 기억하자