코딩테스트 준비 - 가장 큰 수

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : Programmers

• 문제 : 가장 큰 수

• 사용언어 : C#

• 난이도 : 중하

• 풀이시간 : 1h13m

• 유형 : 정렬, 수 비교, 배열

문제 설명

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"

문제 풀이 접근

이 문제에선 삽질을 많이해서 여러번 정답을 들이밀면서 해결해보았다.
1. 모든 조합을 구한 뒤, 큰 수 부터 정렬하여 구하는 방법
2. 문제에서 원소 크기는 1000 으로 고정되었기 때문에, 자릿 수를 10000만의 자리까지 끌고 올라와서 정렬하여 비교하는 방법

먼저, 1번은 효율성에서 좋지 않아 보인다. 일단 모든 조합수를 구하는 데 있어서, O(N^2) 이 들 수 밖에 없다. 모든 원소의 값을 다 구한 뒤 정렬도 수행해야하기 때문이다.
결국 O(N^2) + O(N Log N) 의 시간복잡도로 가정된다. ( 편의상 전부 적어보았음 )

그렇다면 2번의 방법은 어떤게 다른가?
2번은 원소의 수를 잠시 5자리 이상의 수로 연산을한 뒤 정렬을 하면, 1번에서 O(N^2)는 안들고 정렬에 대한 시간 복잡도인 +O(N Log N) 정도만 들겠다.

그러면 수를 정렬하는 방법은 단순히 [6,10,2] 등과 같이 수가 다 다르다면 상관은 없을 수 있는데,
[3,3000] 과 같이 앞자리가 같은수는 결국 3 * 10000 , 3000 * 10 을 하면 결국 30000으로 같다.
그렇기 때문에 자릿수를 맞추는 것은 수를 문자열로 바꾼 후 문자열의 길이만큼 Loop하여 추가한다.
그러면 33333 , 30003 이기 때문에, 3이 더 큰수로 나올 것이다.

이런 아이디어로 비교를 하여 정렬을 하게된다면 정답을 찾을 수 있다.

문제의 플로우는 아래와 같다.
1. Tuple을 이용하여, Key : 6자리 변경 수 , Value : 원래 수
2. Key 기준으로 정렬
3. List의 처음부터 끝까지 원래 수를 StringBuilder 에 Append 하면서 추가.
4. 그리고 Int32.Parse로 캐스팅하여 반환

정답 작성 코드 (C#)

using System;
using System.Text;
using System.Collections.Generic;

public class Solution {
    public string solution(int[] numbers) {
        string answer = "";
        int isZero = 0;

        if(numbers.Length == 1)
        {
            return numbers[0].ToString();
        }
        
        for(int i = 0; i < numbers.Length; ++i)
        {
            if(numbers[i] == 0)
                ++isZero;
        }
        
        if(isZero == numbers.Length)
        {
            answer = "0";
            return answer;
        }
            
        
        // 모두 100000의 숫자로 변경해서 체크.
        List<Tuple<int,int>> list = new List<Tuple<int,int>>();
        
        for(int i = 0; i < numbers.Length; ++i)
        {            
            int valueInt = numbers[i];
            int makeInt = MakeValue(valueInt);
            
            list.Add(new Tuple<int,int>(makeInt,valueInt));
        }
        
        var toArr = list.ToArray();
        
        Array.Sort(toArr, (a,b) => {return b.Item1.CompareTo(a.Item1);});
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < toArr.Length; ++i)
        {
            var element = toArr[i];
            sb.Append(element.Item2);
        }
            
        answer = sb.ToString();
        return answer;
    }
    
    public int MakeValue(int valueInt)
    {
        int ret = 0;
        String valueString = valueInt.ToString();
        StringBuilder sb = new StringBuilder();
        int intIndex = 0;
        
        while(sb.Length != 6) // 비교는 10만으로 비교, 즉 6자리 수로 비교하겠다.
        {
            if(valueString.Length == intIndex)
                intIndex = 0;
            
            
            char element = valueString[intIndex];
            sb.Append(element);
            ++intIndex;
        }
        
        ret = Int32.Parse(sb.ToString());
        return ret;
    }
}

코드 결과