CodingTest

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/challenges?order=recent">Programmers</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://school.programmers.co.kr/learn/courses/30/lessons/42746">가장 큰 수</a></li><li>사용언어 : C#</li><li>난이도 : 중하</li><li>풀이시간 : 1h13m</li><li>유형 : 정렬, 수 비교, 배열</li></ul><h6>문제 설명</h6>0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.<h5>제한 사항</h5><ul><li>numbers의 길이는 1 이상 100,000 이하입니다.</li><li>numbers의 원소는 0 이상 1,000 이하입니다.</li><li>정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.</li></ul><h5>입출력 예</h5>numbers return [6, 10, 2] "6210" [3, 30, 34, 5, 9] "9534330"<h3>문제 풀이 접근</h3>이 문제에선 삽질을 많이해서 여러번 정답을 들이밀면서 해결해보았다. 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로 캐스팅하여 반환<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">

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

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

취준생 일지

<h3>다시푸는 코딩 테스트 준비 일지</h3><ul><li>응시 사이트 :<a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/"> LeetCode</a></li><li>문제 : <a target="_blank" rel="noopener noreferrer nofollow" href="https://leetcode.com/problems/smallest-number-in-infinite-set/">Smallest Number in Infinite Set</a></li><li>사용언어 : C#</li><li>난이도 : 중</li><li>풀이시간 : 35m</li><li>유형 : 정렬리스트, 클래스 구현, 우선순위 큐, 힙 </li></ul>You have a set which contains all positive integers&nbsp;<code spellcheck="false">[1, 2, 3, 4, 5, ...]</code>.Implement the&nbsp;<code spellcheck="false">SmallestInfiniteSet</code>&nbsp;class:<ul><li><code spellcheck="false">SmallestInfiniteSet()</code>&nbsp;Initializes the&nbsp;SmallestInfiniteSet&nbsp;object to contain&nbsp;all&nbsp;positive integers.</li><li><code spellcheck="false">int popSmallest()</code>&nbsp;Removes&nbsp;and returns the smallest integer contained in the infinite set.</li><li><code spellcheck="false">void addBack(int num)</code>&nbsp;Adds&nbsp;a positive integer&nbsp;<code spellcheck="false">num</code>&nbsp;back into the infinite set, if it is&nbsp;not&nbsp;already in the infinite set.</li></ul>&nbsp;Example 1:<pre spellcheck="false"><code>Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1); // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
 // is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.
</code></pre>&nbsp;Constraints:<ul><li><code spellcheck="false">1 &lt;= num &lt;= 1000</code></li><li>At most&nbsp;<code spellcheck="false">1000</code>&nbsp;calls will be made&nbsp;in total&nbsp;to&nbsp;<code spellcheck="false">popSmallest</code>&nbsp;and&nbsp;<code spellcheck="false">addBack</code>.</li></ul><h3>문제 풀이 접근</h3>이 문제는, LeetCode에서만 볼 수 있는 느낌의 유형이다. 아직까지 문제를 많이 풀어보진 않았지만, 이런 클래스 구현에 대한 문제는 LeetCode에서밖에 보지 못했다.문제를 보고 가장 첫 접근은, 리스트 만들고 서치하려고 했으나, 역시 이 문제에 대한 습득이 아직 덜 됐다고 느꼈다. 분명 최소요소를 찾고 pop하고 하는건 우선순위 큐, 힙, 정렬리스트 쪽으로 생각을 먼저했어야 됐는데, 리스트만 생각나는건 아직 경험이 부족한 것 같다. 어쨌건, 문제를 정렬리스트로 활용하여 풀었고, 크게 어려운 문제는 아니었다.이 문제의 해결 플로우, 1. 문제의 제약 조건, 1000까지 숫자를 넣기때문에, Addback 에서 미리 있다면 추가하지 않는것이 필요하다. 즉, 정렬리스트에 1000까지 모든 수를 끼워넣은 리스트를 세팅한다. 2. PopSmallList는 단순히 최소 요소를 리턴한다. 3. AddBack 은 있다면 딱히 할 것이 없다. ( 이것 때문에 1번에서 1000까지 세팅하는 것이다. )<h3>정답 작성 코드 (C#)</h3><pre spellcheck="false"><code>public class SmallestInfiniteSet {
 
 public SortedSet&lt;int&gt; sortSet;

 public SmallestInfiniteSet() {
 sortSet = new SortedSet&lt;int&gt;();
 
 for(int i = 1; i &lt;= 1000; ++i)
 sortSet.Add(i);
 
 }
 
 public int PopSmallest() {
 
 var ret = -1;
 
 if(sortSet.Count &gt; 0)
 {
 ret = sortSet.Min;
 sortSet.Remove(sortSet.Min);
 }
 
 return ret;
 }
 
 public void AddBack(int num) {
 if(sortSet.Contains(num) == true)
 return;
 
 sortSet.Add(num);
 }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.PopSmallest();
 * obj.AddBack(num);
 */</code></pre><h3>코드 결과</h3><img src="https://image.until.blog/sin0105/article/1722871595406" alt="until-1181">

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