[코딩테스트 일지 - 99클럽] 1일차 - 가장 큰 수

코딩 테스트 준비 일지 1 일차

• 문제 : 가장 큰 수

  • https://school.programmers.co.kr/learn/courses/30/lessons/42746

• 난이도 : 중

문제

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();
    }
}