코딩 테스트 준비 일지 1 일차
문제 : 가장 큰 수
난이도 : 중
문제
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
numbers return
[6, 10, 2] "6210"
[3, 30, 34, 5, 9] "9534330"
문제 풀이 접근
먼저, 단순한 문제인것으로 확인하여 "정렬" 이라고 써져있는 것만 보고 그냥 다 정렬 돌려버리고 StringBuilder클래스의 Append 를 이용해서 문자열 더하고 Int.Parse 로 정수로 돌려서 크면 무조건 가지고 있는 Int 형 저장변수를 갱신하여 답을 뽑아내려고 했다.
이렇게하면 1번 TC는 패스할 수 있었으나, 2번을 패스할 수 없었다.
1시간 넘게 고민을 하다 결국 여러 풀이들을 참조하게 되었고, 3번 곱해서 아스키 코드 어쩌구.. 이런 풀이들이 정확하게 이해가 안가서 다른 방식을 찾았다.
정렬을 하면서 비교 수 A , B 를 더하여 A+B, B+A 결과를 판단하여 오름차순으로 정렬하였다.
(내림차순으로 하면 바로 출력하면 되는데, 귀찮아서 최종 연산단에서 뒤부터 앞으로 더했다.)
여기까지 적용할 경우, 11번 TC에서 실패가 뜨는것을 확인할 수 있고, 11번 TC는 [0,0] => 0 의 케이스를 추가하여 코드에 맞춰 수정진행했다.
11번 케이스는 내가 오름차순으로 넣었기 때문에, 마지막에 0 으로 들어가있는지 판단을 하는것으로 이 수의 배열이 0이 제일 크다는 것을 확인할 수 있고, 이런 TC일 경우 0으로 리턴하게되면 쉽게 회피할 수 있다.
작성 코드 ( C# )
using System;
using System.Text;
public class Solution
{
public string solution(int[] numbers)
{
string answer = "";
Combination(ref numbers);
Print(ref numbers, out answer);
return answer;
}
public static void Combination(ref int[] arrStr)
{
Array.Sort(arrStr, (int a, int b) =>
{
StringBuilder aSB = new StringBuilder();
StringBuilder bSB = new StringBuilder();
aSB.Append(a);
aSB.Append(b);
bSB.Append(b);
bSB.Append(a);
int aValue = int.Parse(aSB.ToString());
int bValue = int.Parse(bSB.ToString());
return aValue.CompareTo(bValue);
});
}
public static void Print(ref int[] arrStr, out string result)
{
if (arrStr[arrStr.Length - 1] == 0)
{
result = "0";
return;
}
StringBuilder sb = new StringBuilder();
for (int i = arrStr.Length - 1; i >= 0; --i)
sb.Append(arrStr[i].ToString());
result = sb.ToString();
}
}