[Programmers] 숫자 짝꿍

두 정수 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 함수를 완성해주세요

 

풀이 아이디어

문제를 읽고 나서 어떤 수식이 떠오르진 않았고 주어진 X, Y가 문자열이니 각 문자를 카운팅 한 다음 공통된 문자를 뽑은 다음 공통된 문자에서 다시 각 X, Y에서 가진 최솟값을 추출해서 제출하면 되지 않나라고 생각했다.

아이디어를 통해서 필요한 건 카운팅을 하기 위한 함수와 교집합을 추출해 내기 위한 연산이었다. 먼저 카운팅을 하기 위한 함수는 다음과 같이 직접 작성했다. 

def get_count_dict(numbers):
    result = {}
    for number in numbers:
        if number not in result:
            result[number] = 1
        else:
            result[number] += 1
    return result

매개변수가 list일 때 각 원소의 개수를 구하는 코드이다. dictionary에 존재하지 않을 때 0이 아니라 1부터 카운팅하는 이유는 나중에 문자를 추출해서 취합할 때 "문자 * 숫자"라는 표현을 적용하기 위함이었다.

set은 기본 자료구조이니 설명은 생략하겠다. 

Code

def get_count_dict(numbers):
    result = {}
    for number in numbers:
        if number not in result:
            result[number] = 1
        else:
            result[number] += 1
    return result


def solution(X, Y):
    number_1 = X
    number_2 = Y

    number_1_count = get_count_dict(number_1)
    number_2_count = get_count_dict(number_2)

    intersection = set(number_1_count.keys()).intersection(number_2_count.keys())

    if not intersection:
        return "-1"

    if len(intersection) == 1:
        return str(intersection.pop())

    answer = ""
    for each in intersection:
        f_number = number_1_count[each]
        s_number = number_2_count[each]

        min_number = min(f_number, s_number)

        answer += each * min_number

    return ''.join(sorted(answer, reverse=True))

 

실행 결과 

list와 dict 그리고 문자열 연산에 코스트가 가중되어있다 보니 공간 복잡도가 올라가는 양상이 보였다.