C# 코딩테스트 강좌, 수를 묶어서 최댓값 만들기

이번 강좌에서는 코딩 테스트에서 자주 출제되는 문제 중 하나인 ‘수를 묶어서 최댓값 만들기’ 문제를 다룰 것입니다. 이 문제는 주어진 수들을 조합하여 가능한 최대의 수를 만드는 과정을 다룹니다. 그리고, 이를 C# 언어를 통해 해결하는 방법을 단계별로 설명하겠습니다.

문제 설명

여러 개의 양의 정수들이 주어질 때, 이 숫자들을 조합해서 만들 수 있는 가장 큰 수를 반환하는 함수를 작성하시오. 예를 들어, 주어진 숫자들이 [3, 30, 34, 5, 9]라면, 이들을 적절히 조합하여 만들 수 있는 가장 큰 수는 9534330입니다.

입력 형식

하나의 정수 배열 numbers가 주어집니다. 배열의 크기는 0 이상 100 이하이며, 각 숫자의 길이는 1 이상 10 이하입니다.

출력 형식

모든 숫자를 조합하여 만든 가장 큰 수를 문자열 형태로 반환합니다.

문제 접근법

이 문제를 해결하기 위해서는 몇 가지 접근 방식이 필요합니다.

• 정렬: 주어진 숫자들을 정렬하여 가장 큰 수를 만들어야 합니다. 정렬 기준이 중요하며, 각 숫자를 문자열로 보고 적용할 규칙을 만들어야 합니다.
• 문자열 비교: 두 숫자를 비교할 때, 각각의 숫자가 먼저 오는 경우와 뒤에 오는 경우를 조합하여 누가 더 큰 수가 될지를 판단해야 합니다.

코드 구현

위의 접근법에 따라서 C#으로 문제를 해결하는 코드를 작성해 보겠습니다.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public static string Solution(int[] numbers)
    {
        // 숫자를 문자열로 변환합니다.
        string[] strNumbers = numbers.Select(n => n.ToString()).ToArray();
        
        // 문자열 배열을 정렬합니다.
        Array.Sort(strNumbers, (x, y) => (y + x).CompareTo(x + y));
        
        // 정렬된 배열을 하나의 문자열로 결합합니다.
        string result = string.Join("", strNumbers);
        
        // 만약 결과가 "0"으로 시작하면 0만 반환합니다.
        return result[0] == '0' ? "0" : result;
    }

    static void Main(string[] args)
    {
        int[] numbers = { 3, 30, 34, 5, 9 };
        string answer = Solution(numbers);
        Console.WriteLine(answer);  // 9534330
    }
}
    

코드 설명

위 코드를 좀 더 자세히 살펴보겠습니다.

1. 문자열 변환: 우선 각 숫자를 문자열로 변환한 후 strNumbers라는 배열에 저장합니다. 이는 숫자들을 문자열 형태로 재배열하기 위해 필요합니다.
2. 정렬: Array.Sort 메서드를 사용하여 strNumbers 배열을 정렬합니다. 이때, 정렬 기준으로는 두 숫자 x와 y를 결합하여 큰 순서대로 정렬합니다. (y + x)와 (x + y)를 비교하는 방식으로, 어떤 조합이 큰지를 판단합니다.
3. 결과 결합: 정렬된 숫자들을 string.Join을 사용하여 하나의 문자열로 결합합니다.
4. 최종 확인: 만약 결과 문자열의 첫 번째 문자가 ‘0’이라면 모든 숫자가 0인 경우이므로 ‘0’만 반환합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N log N)입니다. 이는 주어진 숫자 배열을 정렬하는 과정에 소비되는 시간입니다. N은 숫자의 개수를 나타냅니다. 공간 복잡도는 O(N)으로 각 숫자를 문자열로 변환하여 저장하는 배열을 필요로 합니다.

결론

이번 강좌에서는 C#으로 ‘수를 묶어서 최댓값 만들기’ 문제를 해결하는 방법을 살펴보았습니다. 알고리즘 문제를 해결하기 위해서는 문제를 잘 이해하고, 적절한 자료구조와 알고리즘을 선택하는 것이 중요합니다. 다양한 문제를 통해 연습하세요!

추가 연습 문제

여기서 더 나아가 다음의 문제들을 추가로 연습해보는 것을 권장합니다.

• 주어진 숫자들을 조합하여 가능한 모든 경우의 수를 만들고, 그 중 최대값을 찾아보세요.
• 양수 및 음수를 혼합하여 주었을 때, 최댓값을 만드는 알고리즘을 작성해보세요.
• 입력 배열의 크기가 매우 커질 경우, 성능 저하를 방지하기 위한 방법을 모색해 보세요.

참고 자료

이와 같은 알고리즘 문제를 푸는 데는 여러 참고 자료들이 도움이 됩니다. 다음 링크들을 참조해보세요:

• GeeksforGeeks
• LeetCode
• HackerRank