가장 큰 수
문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가[6, 10, 2]라면
[6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고,
이중 가장 큰 수는6210입니다.
0또는 양의 정수가 담긴 배열numbers가 매개변수로 주어질 때,
순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어return하도록solution함수를 작성해주세요.
풀이
public class LargestNumberComposer
{
public static string Solution(int[] numbers)
{
string[] strNumbers = numbers.Select(n => n.ToString()).ToArray();
Array.Sort(strNumbers, new CustomNumberComparer());
// 가장 큰 수가 0이라는 의미이므로, 최종 결과를 "0"으로 반환
if (strNumbers[0] == "0")
{
return "0";
}
return string.Join("", strNumbers);
}
}
// 사용자 정의 비교자 클래스
public class CustomNumberComparer : IComparer<string>
{
/// <summary>
/// 두 문자열 x와 y를 비교하여 어떤 순서로 정렬될지 결정합니다.
/// 이 비교자는 "x가 y보다 앞에 오면 -1", "같으면 0", "y가 x보다 앞에 오면 1"을 반환합니다.
/// </summary>
/// <returns>
/// -1: x가 y보다 앞에 와야 함 (x + y가 y + x 보다 크거나 같음)
/// 1: y가 x보다 앞에 와야 함 (y + x가 x + y 보다 큼)
/// 0: x와 y의 순서가 같아도 무방 (y + x와 x + y가 동일)
/// </returns>
public int Compare(string x, string y)
{
// 핵심 비교 로직: (y+x)와 (x+y)를 비교합니다.
// 예를 들어, x="6", y="10"
// y + x = "10" + "6" = "106"
// x + y = "6" + "10" = "610"
// string.Compare("106", "610")은 "106"이 사전적으로 "610"보다 앞에 오므로, 음수(-1)를 반환합니다.
// Array.Sort는 기본적으로 Compare 결과가 음수이면 x를 y보다 앞에 둡니다.
// 즉, "10"이 "6"보다 앞에 오게 정렬됩니다. (올바른 순서)
// 예를 들어, x="3", y="30"
// y + x = "30" + "3" = "303"
// x + y = "3" + "30" = "330"
// string.Compare("303", "330")은 "303"이 사전적으로 "330"보다 앞에 오므로, 음수(-1)를 반환합니다.
// 즉, "30"이 "3"보다 앞에 오게 정렬됩니다. (올바른 순서)
// 최종적으로 String.Compare(y+x, x+y)를 반환하면
// y+x가 더 크면 양수 반환 -> y가 x보다 앞에 온다.
// x+y가 더 크면 음수 반환 -> x가 y보다 앞에 온다.
// 이 Comparator는 가장 큰 수가 되도록 정렬합니다.
return string.Compare(y + x, x + y);
}
}초기 접근
- 앞선 두 문제 특이한 정렬과 문자열 내 마음대로 정렬하기 문제에서 사용했던 삽입 정렬과 조건을 결합한 방식으로 문제를 해결할 수 있을 것이라고 생각함
public class LargestNumberComposer
{
/*
* 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
* 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고,
* 이중 가장 큰 수는 6210입니다.
* 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때,
* 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
*/
//https://school.programmers.co.kr/learn/courses/30/lessons/42746
public static string Solution(int[] numbers)
{
Stack<string> sortedNums = new Stack<string>();
Stack<string> stashedNums = new Stack<string>();
foreach (int num in numbers)
{
if (sortedNums.Count == 0)
{
sortedNums.Push(num.ToString());
continue;
}
while (TryPush(sortedNums.Peek(), num.ToString()))
{
stashedNums.Push(sortedNums.Pop());
if (sortedNums.Count == 0)
break;
}
sortedNums.Push(num.ToString());
while (stashedNums.Count > 0)
sortedNums.Push(stashedNums.Pop());
}
var arr = sortedNums.Reverse().ToArray();
string answer = "";
foreach (var numStr in arr)
{
//Console.WriteLine(numStr);
answer += numStr;
}
return answer;
}
private static bool TryPush(string topNumStr, string inputNumStr)
{
int length = topNumStr.Length > inputNumStr.Length ? inputNumStr.Length : topNumStr.Length;
for (int i = 0; i < length; i++)
{
int topNum = int.Parse(topNumStr[i].ToString());
int inputNum = int.Parse(inputNumStr[i].ToString());
//각각의 자리수를 비교
//첫째 자리부터 비교했을때 첫째자리가 가장 큰 숫자가 제일 앞에 옴
//첫째 자리가 같을 경우 다음 자리수를 비교해 더 큰 숫자가 앞에 와야함
//기존에 있는 숫자의 자리수가 더 크면 기존 스택에서 빼는 것을 멈추고 새로운 숫자를 추가
if (topNum > inputNum)
return false;
//해당 자리수의 숫자가 같으면서 새로 추가하려는 숫자의 자리수가 더 작으면 기존 숫자를 빼고 추가
if (topNum == inputNum && topNumStr.Length < inputNumStr.Length)
{
if (int.Parse(inputNumStr[i+1].ToString()) > topNum)
return true;
else
return false;
}
}
return true;
}
}- 첫번째 자릿수부터 각 자릿수의 숫자를 비교해 자릿수가 큰 숫자를 보다 앞에 위치하도록 함
- 그러나
3과30을 비교하는 경우와3과34를 비교하는 경우에 첫번째는3이 앞에 오는330이 크지만, 두번째 경우는3이 뒤에 오는343이 더 큰 숫자를 구성할 수 있음
따라서 자리수가 다른 경우에는 앞서 비교한 숫자보다 다음 자리에 위치한 숫자가 더 클 경우 보다 앞에 위치해야하는 경우가 발생한다고 생각 - 다만 이 경우까지 고려해도 모든 숫자들을 비교하는데 있어 올바른 정답을 찾지 못해 새로운 로직의 필요성을 느낌
정렬 규칙 개선
private static bool TryPush(string topNumStr, string inputNumStr) // topNumStr 이 inputNumStr 보다 뒤에 와야 True
{
string str1 = topNumStr + inputNumStr; // 기존 숫자 + 새 숫자
string str2 = inputNumStr + topNumStr; // 새 숫자 + 기존 숫자
return string.Compare(str2, str1) > 0; // str2가 str1보다 크면 true
}기존 숫자 + 새로운 숫자순서의 조합과 그 반대의 숫자 중 기존 숫자가 뒤에 오는 숫자 조합이 더 클 경우 기존 숫자를 제거하고 새로운 숫자를 추가하도록 함
삽입 정렬의 시간 복잡도 문제
- 해당 방법을 통해 정렬 규칙을 개선했지만 여전히 시간 복잡도가 크다는 문제가 발생
이를 해결하기 위해 사용자 정의 비교자를 사용하여 내장된Sort함수를 사용해 복잡도를 개선할 수 있음을 조사를 통해 알게 됨
public class CustomNumberComparer : IComparer<string>
{
public int Compare(string x, string y)
{
return string.Compare(y + x, x + y);
}
}- 기본적으로 사용자 정의 비교자 클래스는
IComparer인터페이스를 상속받아Compare요소를 정의하고 있음 Compare함수는 두 문자열x와y를 비교해x가 더 앞에 와야할 경우 -1을,y가 더 앞에 와야할 경우 1을 순서가 상관 없을 경우에는 0을 반환
사용자 정의 비교자 사용
public static string Solution(int[] numbers)
{
// 1. int 배열을 string 배열로 변환
string[] strNumbers = numbers.Select(n => n.ToString()).ToArray();
// 2. 사용자 정의 비교자(Comparer)를 사용하여 정렬
Array.Sort(strNumbers, new CustomNumberComparer());
// 3. 엣지 케이스 처리: 모든 숫자가 0인 경우 ("0", "0", "0" -> "0")
// 정렬 결과의 첫 번째 요소가 "0"이면, 모든 원소가 0이거나 (예: [0, 0, 0] -> ["0", "0", "0"])
// 가장 큰 수가 0이라는 의미이므로, 최종 결과를 "0"으로 반환
if (strNumbers[0] == "0")
{
return "0";
}
// 4. 정렬된 문자열들을 이어붙여서 최종 결과 반환
// string.Join은 배열의 요소들을 특정 구분자 없이 하나의 문자열로 합침
return string.Join("", strNumbers);
}- 주어진
int배열을string배열로 변환
Select를 통해 배열 내 모든 요소에ToString()을 실시하고 이를 새로운 배열strNumbers에 저장 Sort시에 기존에 정의한 사용자 정의 비교자를 사용Join을 통해strNumbers의 요소들을 합침
정리
- 사용자 정의 비교자라는 새로운 방법을 알게 되어 앞서 삽입 정렬을 통해 풀었던 문제들도 사용자 정의 비교자를 생성하여 문제를 해결하면 보다 간단하면서 효율적이게 문제를 풀 수 있을 것 같음
