CodingTest

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li><p>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></p></li><li><p>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42746">가장 큰 수</a></p></li><li><p>사용언어 : C#</p></li><li><p>난이도 : 중하</p></li><li><p>풀이시간 : 1h13m</p></li><li><p>유형 : 정렬, 수 비교, 배열</p></li></ul><h6><strong>문제 설명</strong></h6><p>0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.</p><p>예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.</p><p>0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.</p><h5>제한 사항</h5><ul><li><p>numbers의 길이는 1 이상 100,000 이하입니다.</p></li><li><p>numbers의 원소는 0 이상 1,000 이하입니다.</p></li><li><p>정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.</p></li></ul><h5>입출력 예</h5><p>numbers return <br>[6, 10, 2] "6210"<br>[3, 30, 34, 5, 9] "9534330"</p><h3>문제 풀이 접근</h3><p>이 문제에선 삽질을 많이해서 여러번 정답을 들이밀면서 해결해보았다.<br>1. 모든 조합을 구한 뒤, 큰 수 부터 정렬하여 구하는 방법<br>2. 문제에서 원소 크기는 1000 으로 고정되었기 때문에, 자릿 수를 10000만의 자리까지 끌고 올라와서 정렬하여 비교하는 방법<br><br>먼저, 1번은 효율성에서 좋지 않아 보인다. 일단 모든 조합수를 구하는 데 있어서, O(N^2) 이 들 수 밖에 없다. 모든 원소의 값을 다 구한 뒤 정렬도 수행해야하기 때문이다.  <br>결국 O(N^2) + O(N Log N) 의 시간복잡도로 가정된다. ( 편의상 전부 적어보았음 )<br><br>그렇다면 2번의 방법은 어떤게 다른가?<br>2번은 원소의 수를 잠시 5자리 이상의 수로 연산을한 뒤 정렬을 하면, 1번에서 O(N^2)는 안들고 정렬에 대한 시간 복잡도인 +O(N Log N) 정도만 들겠다. <br><br>그러면 수를 정렬하는 방법은 단순히 [6,10,2] 등과 같이 수가 다 다르다면 상관은 없을 수 있는데, <br>[3,3000] 과 같이 앞자리가 같은수는 결국 3 * 10000 , 3000  * 10 을 하면 결국 30000으로 같다. <br>그렇기 때문에 자릿수를 맞추는 것은 수를 문자열로 바꾼 후 문자열의 길이만큼 Loop하여 추가한다. <br>그러면 33333 , 30003 이기 때문에, 3이 더 큰수로 나올 것이다. <br><br>이런 아이디어로 비교를 하여 정렬을 하게된다면 정답을 찾을 수 있다. <br><br>문제의 플로우는 아래와 같다. <br>1. Tuple을 이용하여, Key : 6자리 변경 수 , Value : 원래 수 <br>2. Key 기준으로 정렬 <br>3. List의 처음부터 끝까지 원래 수를 StringBuilder 에 Append 하면서 추가. <br>4. 그리고 Int32.Parse로 캐스팅하여 반환</p><h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>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 &lt; numbers.Length; ++i)
        {
            if(numbers[i] == 0)
                ++isZero;
        }
        
        if(isZero == numbers.Length)
        {
            answer = "0";
            return answer;
        }
            
        
        // 모두 100000의 숫자로 변경해서 체크.
        List&lt;Tuple&lt;int,int&gt;&gt; list = new List&lt;Tuple&lt;int,int&gt;&gt;();
        
        for(int i = 0; i &lt; numbers.Length; ++i)
        {            
            int valueInt = numbers[i];
            int makeInt = MakeValue(valueInt);
            
            list.Add(new Tuple&lt;int,int&gt;(makeInt,valueInt));
        }
        
        var toArr = list.ToArray();
        
        Array.Sort(toArr, (a,b) =&gt; {return b.Item1.CompareTo(a.Item1);});
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i &lt; 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;
    }
}</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1724065391054" alt="until-1246"><p></p>

혼자서 다시푸는 코딩테스트 준비 일지 - 13