C# 코딩테스트 강좌, 최솟값 찾기 2

문제 설명

주어진 정수 배열에서 두 개의 가장 작은 숫자를 찾고, 그들의 합을 반환하는 함수를 작성하시오.

예시:

            입력: [3, 1, 4, 1, 5, 9, 2, 6, 5]
            출력: 2 (1 + 1)
            

같은 숫자가 포함되어 있을 경우, 같은 숫자를 두 번 사용할 수 있습니다.

문제 접근 방식

이 문제를 해결하기 위한 몇 가지 접근 방식을 생각해볼 수 있습니다.

1. 정렬을 이용한 방법

배열을 정렬한 후 첫 번째 두 개의 요소를 가져와서 그들의 합을 계산할 수 있습니다.

2. 이중 반복문

이중 반복문을 이용하여 두 개의 정수를 직접 비교하며 최솟값을 찾는 방법도 가능합니다. 하지만 이 방법은 비효율적일 수 있습니다.

3. 단일 반복문을 이용한 최솟값 찾기

단일 반복문을 통해 두 개의 최솟값을 찾는 방법이 가장 효율적입니다. 배열을 한 번만 순회하면서 최솟값을 발견할 수 있습니다.

해결 방법 1: 정렬을 이용한 방법

using System;
using System.Linq;

public class Solution {
    public static int FindTwoMinSum(int[] arr) {
        // 배열을 정렬합니다.
        Array.Sort(arr);
        // 두 개의 가장 작은 숫자의 합을 반환합니다.
        return arr[0] + arr[1];
    }
}

// 사용 예시
public class Program {
    public static void Main() {
        int[] numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5};
        Console.WriteLine(FindTwoMinSum(numbers)); // 출력: 2
    }
}
            

이 방법은 직관적이며 이해하기 쉽지만, 시간 복잡도가 O(n log n)으로 비교적 느릴 수 있습니다. 특히 배열 크기가 큰 경우에는 성능 저하가 우려됩니다.

해결 방법 2: 이중 반복문을 이용한 방법

using System;

public class Solution {
    public static int FindTwoMinSum(int[] arr) {
        int min1 = int.MaxValue;
        int min2 = int.MaxValue;

        foreach (int num in arr) {
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        
        return min1 + min2;
    }
}

// 사용 예시
public class Program {
    public static void Main() {
        int[] numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5};
        Console.WriteLine(FindTwoMinSum(numbers)); // 출력: 2
    }
}
            

이 방법의 시간 복잡도는 O(n)으로 더 효율적이며, 배열을 한 번만 순회하면서 두 개의 최솟값을 찾습니다. 위 방법은 성능면에서도 우수하지만, 약간의 코드 복잡성이 있습니다.

결론

이 글에서는 C#을 사용하여 주어진 배열에서 두 개의 최솟값을 찾는 문제를 해결하는 다양한 방법을 살펴보았습니다. 처음 방법인 정렬을 이용한 방법은 구현은 간단하지만, 성능 면에서는 좋지 않았습니다. 그에 반해, 단일 반복문을 이용한 방법은 효율적이고 실용적이었습니다. 이러한 문제들은 알고리즘 시험에서 자주 출제되므로, 연습을 통해 충분한 이해와 습득이 필요합니다.

다양한 문제 해결 방법을 익혀두면, 코딩 테스트뿐만 아니라 실제 개발 환경에서도 많은 도움이 될 것입니다. 감사합니다.