[항해 99 코테 스터디] 숫자짝궁

문제 설명

두 정수 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의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

입출력 예

X	Y	result
"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

 

주안점

보통 다른 문제에서는 예시 케이스만으로 증명할수 없는 경우(부정확한 결과값) 이 문제인데, 이 문제 같은 경우는 3,000,000 자릿수 까지 정수가 들어갈 수 있다는게 문제였다.

 

처음에는 반복문을 줄여야 하나 삽질을 계속 했는데... 생각해보니 자료구조를 효율적으로 만들면 상수시간내에 끝낼 수 있지 않을까 싶어 수정했다. (ㅠㅠ 지난번엔 반대로 하더니만...)

 

제출코드(시간초과)

def solution(X, Y):
    X = list(str(X))
    Y = str(Y)
    lnY = len(Y)
    lnX = len(X)
    nums = []
    lnN = 0
    for i in range(0, lnY):
        y_item = Y[i]
        for j in range(0, lnX):
            x_item = X[j]
            if(x_item == y_item):
                nums.append(y_item)
                X.pop(j)
                lnX -= 1
                lnN += 1
                break
    nums.sort(reverse=True)
    if(lnN == 0): nums = '-1'
    if(nums[0] == '0'): nums = '0'
    else: nums = ''.join(nums)
    return nums

 

답안코드

digit1 = [0 for i in range(10)];
digit2 = [0 for i in range(10)];
digit = [0 for i in range(10)];
num = ''
def solution(X, Y):
    global num
    strX = str(X)
    strY = str(Y)
    for x in range(len(strX)):
        d = int(strX[x])
        digit1[d] += 1
    for y in range(len(strY)):
        d = int(strY[y])
        digit2[d] += 1
    for d2 in range(10):
        b = digit2[d2]
        a = digit1[d2]
        if(b == 0): continue
        mn = min(a, b)
        if(a > 0): digit[d2] = mn
    for i in range(9,-1,-1):
        if digit[i] != 0:
            num += (str(i) * digit[i])
    if num == '':
        num = '-1'
    elif num[0] == '0':
        num = '0'
    return num