C# 프로그래머스 Lv2 가장 큰 수

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbersreturn

"[6, 10, 2]"	"6210"
"[3, 30, 34, 5, 9]"	"9534330"

 

 

풀이

처음에는 접근을 만들수 있는 모든 숫자를 만들어서 저장해놓고 가장 큰 수를 리턴하려고 했으나 문제는 재귀함수에 대한 이해가 부족하고 문제풀이에 대한 시간제한이 있어서 다른 방법을 찾았다.

 

문제 이해의 핵심은 3 , 30 , 34 가 있을때 34가 제일 앞에 그 다음은 3 그 다음은 30이 와야 가장 큰 수가 나온다.

첫 접근은 3개 모두 1의 자리를 만들어서 (예 33/10, 333/100, 3333/1000) 비교해서 앞에 같다 붙일라고 했는데 이 방식으로 하면 3과 30이 같아진다. 따라서 string비교 메서드를 사용했다.

 

(x+y), (y+x) 문자열 그대로

 "3"+"30", "30"+"3" 중에서 당연히 330이 더 크다.

Compare 인터페이스를 위 형식과 같이 정렬한다.

 

처음에는 매개변수인 numbers를 스트링 배열 string_numbers 로 저장한 다음

Array.Sort(string_numbers, (x,y) => string.Compare(y+x,x+y)) 로 했으나 시간제한 때문에 아래와 같이 즉석해서 string배열로 바꿔주고 string을 기준으로 정렬한다. 

 

StringBuilder를 사용해서 시간제한을 줄였다.

 

sb.Append로 정렬된 numbers를 ToString으로 붙여주고 answer에 다시 복사한다. 

 

여기서 한가지 "00000" 으로 입력이 들어온다면 출력은 "0"이 되야 하므로 string answer에서 0의 개수가 numbers의 길이랑 똑같다면 "0"을 리턴하고 그 외의 경우엔 그냥 리턴한다.

public class Solution {
    public string solution(int[] numbers) {
            string answer = "";
            StringBuilder sb = new StringBuilder();
            string[] temp_string = new string[numbers.Length];
            int[] test_int = new int[numbers.Length];
        
            Array.Sort(numbers, (x, y) => string.Compare(y.ToString()+x.ToString(),x.ToString()+y.ToString()));
            
            for (int i = 0; i < numbers.Length; i++)
            {
                sb.Append(numbers[i].ToString());
            }
            answer = sb.ToString();
            int count = 0;
            foreach (var item in answer)
            {
                if (item == '0')
                    count++;
            }
            
            if (count == numbers.Length)
                return "0";
            
            else
                return answer;
    }
}