20231005

I. 숫자 짝궁

 

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

 

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

 

제한사항
3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
X, Y는 0으로 시작하지 않습니다.
X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

 

!! 나의 풀이 (1차)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string solution(string X, string Y) {
        string answer = "";
        int[] intXArray = StringToIntArray(X);
        int[] intYArray = StringToIntArray(Y);
        answer = CountElement(intXArray, intYArray);
        return answer;
    }
    
    public int[] StringToIntArray(string X)
    {
        char[] charXArray = X.ToCharArray();
        int[] intXArray = Array.ConvertAll(charXArray, s => (int)Char.GetNumericValue(s));
        return intXArray;
    }
    
    public string CountElement(int[] intArray, int[] intCompareArray)
    {
        var numCount = new int[10];
        string returnCalc = "";
        for (int i = 0; i < 10; i++)
        {
            int cnt = intArray.Where(s => s == i).Count();
            int cntComp = intCompareArray.Where(s => s == i).Count();
            int cntMin = Math.Min(cnt, cntComp);
            if (i == 0 && cntMin > 0)
            {
                returnCalc += "0";
            }
            else
            {
                for (int j = 0; j < cntMin; j++)
                {
                    returnCalc += (i).ToString();
                }
            }
        }
        
        string ans = new string(returnCalc.Reverse().ToArray());
        if (ans == "")
        {
            ans = "-1";
        }
        return ans;
    }
}

 

>

 

 

틀린 이유

 

 1. 실패

 

   "00" 을 "0" 으로 반환하라고 요구했었기에, 다음과 같은 코드를 작성하였다.

 

            if (i == 0 && cntMin > 0)
            {
                returnCalc += "0";
            }

 

     작성한 코드대로라면, 공통된 부분이 0 이외에도 다른 숫자가 있고, 0이 중복된 경우에도 일괄적으로 0을 한번만 표시하였기 때문에, 잘못된 값을 반환하게 된다.

 

 2. 시간 초과

 

    주어진 조건에서, 파라미터로 주어진 문자열의 자릿수가 최대 300만개라고 제시하였다.

    내가 풀이한 방식은, 각 문자열을 문자의 배열로 변환한 후, 각각의 요소에 대해 다시, 숫자로 변환하는 방식을 하였다.

    최대의 문자열이 주어졌다고 가정하면,

    주어진 문자열을 숫자의 배열로 만들기 위해 300만개의 문자열을 300만번 연산한 후, 또다시 300만번 연산하였다.

   

    public int[] StringToIntArray(string X)
    {
        char[] charXArray = X.ToCharArray();
        int[] intXArray = Array.ConvertAll(charXArray, s => (int)Char.GetNumericValue(s));
        return intXArray;
    }

   

    거기에, 변환한 문자열에 대해, 모든 요소를 0 ~ 9까지 비교하는 연산을 하였다.

 

        for (int i = 0; i < 10; i++)
        {
            int cnt = intArray.Where(s => s == i).Count();
            // 생략..

 

    연산을 반복한 점이, 시간 초과를 일으킨 것이라 생각하였다.

    그래서 반복을 최소화하는 방향으로 다시 주어진 문제를 풀었다.

 

 

!! 나의 풀이 (2차)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string solution(string X, string Y) {
        string answer = "";
        int[] xNum = CountNum(X);
        int[] yNum = CountNum(Y);
        bool isAllZero = false;
        for (int i = 0; i < xNum.Length; i++)
        {
            int minNum = Math.Min(xNum[i], yNum[i]);
            if (!isAllZero && i == 9 && minNum > 0)
            {
                answer += "0";
            }
            else
            {
                if (minNum > 0)
                {
                    isAllZero = true;
                }
                for (int j = 0; j < minNum; j++)
                {
                    answer += (9-i).ToString();
                }
            }
            
            
        }

        if (answer == "")
        {
            answer = "-1";
        }
        
        
        return answer;
    }
    
    public int[] CountNum(string str)
    {
        int[] cntNum = new int[10];
        for (int i = 0; i < str.Length; i++)
        {
            cntNum[9 - int.Parse(str[i].ToString())] += 1;
        }
        return cntNum;
    }
}

 

>

 

 

 2. 시간 초과

 

    연산의 반복을 방지하기 위해, 문자열을 한번만 순회하면서, 10칸 짜리 정수형 배열을 만들어, 각 index에 해당하는 숫자의 횟수를 값으로 가지게 함. 문제에서는 가장 큰 값을 반환하라고 요구했기 때문에, 9부터 0까지의 숫자에 해당하는 횟수를 값으로 배열에 지니게 함.

 

    public int[] CountNum(string str)
    {
        int[] cntNum = new int[10];
        for (int i = 0; i < str.Length; i++)
        {
            cntNum[9 - int.Parse(str[i].ToString())] += 1;
        }
        return cntNum;
    }

 

    문자열의 경우, 문자열에 문자를 추가하거나 변경할 때마다, 원래 문자열을 복사하고 새로운 문자를 추가하는 과정을 거침. 이 때문에, 시간 복잡도가 O(n)임.

 

            else
            {
                if (minNum > 0)
                {
                    isAllZero = true;
                }
                for (int j = 0; j < minNum; j++)
                {
                    answer += (9-i).ToString();
                }
            }

 

    문자로 이루어진 리스트에 문자를 추가하는 경우, 리스트는 동적으로 크기가 조절되는 배열이므로 시간 복잡도가 O(1)임.

또한, 숫자를 문자로 바꿀 때마다 연산을 요구하므로, 각 숫자를 문자형으로 가진 배열을 추가하여, 해당 배열의 값을 추가하는 방식으로 바꿈.

 

	string[] floor = new string[10] {"9", "8", "7", "6", "5", "4", "3", "2", "1", "0"};
    //... 생략 ...

		else
            {
                if (minNum > 0)
                {
                    isAllZero = true;
                }
                for (int j = 0; j < minNum; j++)
                {
                    ansList.Add(floor[i]);
                }
            }

 

!! 나의 풀이 (최종)

 

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string solution(string X, string Y) {
        string answer = "";
        int[] xNum = CountNum(X);
        int[] yNum = CountNum(Y);
        string[] floor = new string[10] {"9", "8", "7", "6", "5", "4", "3", "2", "1", "0"};
        var ansList = new List<string>();
        bool isAllZero = false;
        
        for (int i = 0; i < xNum.Length; i++)
        {
            int minNum = Math.Min(xNum[i], yNum[i]);
            if (!isAllZero && i == 9 && minNum > 0)
            {
                ansList.Add("0");
            }
            else
            {
                if (minNum > 0)
                {
                    isAllZero = true;
                }
                for (int j = 0; j < minNum; j++)
                {
                    ansList.Add(floor[i]);
                }
            }
        }

        answer = String.Join("",ansList);
        if (answer == "")
        {
            answer = "-1";
        }

        return answer;
    }

    public int[] CountNum(string str)
    {
        int[] cntNum = new int[10];
        for (int i = 0; i < str.Length; i++)
        {
            cntNum[9 - int.Parse(str[i].ToString())] += 1;
        }
        return cntNum;
    }
}