프로그래머스 - 가장 큰 수 (속도를 고려한 개선된 풀이)

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

 

 

 

 

여러 개의 int 형 배열을 받았을 때 이를 조합하여 만들 수 있는 가장 큰 수를 string 형식으로 받는 문제이다.

 

이 문제는 Linq를 쓰면 간단하게 해결돼서 딱히 기록할 만한 문제는 아니었지만, 그래도 문제를 푼 이후 조금 더 연산 시간을 단축시키는 법을 찾아서 기록하고자 하였다.

 

 

 

---

 

 

 

처음엔 아래와 같은 방식으로 전체를 돌며 둘을 비교하는 규칙을 지정하여 나열하였지만.

이와 같은 경우 배열의 길이가 큰편이 아니라 시간 초과가 발생하지 않았고 정답 처리가 되었다.

 

public string solution(int[] numbers)
{
    var nums = numbers
        .OrderBy(x => x, Comparer<int>.Create((x,y) =>
        { 
            int xy = int.Parse(x.ToString() + y.ToString());
            int yx = int.Parse(y.ToString() + x.ToString());

            return yx.CompareTo(xy);
        }
        ));

    // 예외처리
    if (nums.First() == 0) return "0";
    return string.Join("",nums);
}

 

 

 

 

해당 방식의 경우 위와 같이 1000ms 를 넘는 정확성 테스트의 결과도 볼 수 있다.

이처럼 OrderBy + 커스텀 메서드 사용하여 두 숫자를 합쳤을 때의 큰 수를 비교하여 문제를 해결하게 되면 보다 넓은 범위를 다 체킹 하며 진행하기에, 이번에는 문제가 없었지만 만약 배열의 길이가 길어진다면 충분히 시간초과도 나올 수 있었다.

 

 

따라서 OrderBy를 진행하기 전 한번 큰 범위에서의 분별 작업을 거쳐서 조금더 비교를 줄이는 게 효율적인 구조라고 판단하여

첫자리 숫자별로의 그룹을 나누는 작업을 아래와 같이 진행하였다.

 

 

 

---

 

 

 

public string solution(int[] numbers)
{
    var nums = numbers
        .OrderByDescending(x => FirstDigit(x))
        .ThenBy(x => x, Comparer<int>.Create((x,y) =>
        { 
            int xy = int.Parse(x.ToString() + y.ToString());
            int yx = int.Parse(y.ToString() + x.ToString());

            return yx.CompareTo(xy);
        }
        ));
        
    // 예외처리
    if(nums.First() == 0) return "0";
    return string.Join("",nums);
}

int FirstDigit(int n)
{
    while (n >= 10)
    {
        n /= 10;
    }
    return n;
}

 

 

조금 더 길어지긴 했지만 가독성이 떨어지는 구조도 아니기에 문제가 없다고 판단했고.

실제로 연산 속도도 아래와 같이 조금 더 빨라진 모습을 볼 수 있었다.

 

 

 

 

기존 1012ms => 844ms