[level 1] 숫자 짝꿍

문제

두 정수 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

1) x와 y의 각 원소를 key, 해당 원소의 개수를 value로 가지는 딕셔너리를 정의한다.

2) 이중 반복문을 돌며 리스트의 key의 공통여부를 확인한다.

3) 만약, 리스트 key가 같다면, key를(key == x, y의 각 원소) 두 딕셔너리에 정의된 value 중 작은 값만큼 same 리스트에 추가한다. 

4) 만약 same 리스트의 길이가 0이라면 answer 값을 -1로 정의한다. 

5) 아니라면 permutation으로 same리스트의 순열을 구한 뒤, 각각의 순열을 int로 바꾸었을 때 가장 큰 값을 구한다. 반복문 후에 max 값을 str로 다시 형변환 한뒤 answer로 지정한다. 

6) 만약 answer를 int로 바꾼 값이 0이라면 answer를 '0'으로 지정한다. 

import itertools

def solution(X, Y):
    X_dict = {}
    Y_dict = {}
    answer = ''
    same = []
    
    for i in X:
        X_dict[i] = list(X).count(i)

    for i in Y:
        Y_dict[i] = list(Y).count(i)
    
    for i in list(X_dict):
        for j in list(Y_dict):
        
            if i == j:
                if X_dict[i] != Y_dict[j]:
                    if X_dict[i] < Y_dict[i]:
                        same.append(i*X_dict[i])
                
                    else:
                        same.append(i*Y_dict[j])
            
                else:
                    same.append(i*X_dict[i])
                


    if len(same) == 0:
        answer = '-1'
               
    else:
        max = 0
        for i in itertools.permutations(same, len(same)):
            coms = int(''.join(i))
        
            if coms > max:
                max = coms
    
        answer = str(max)
    

    if int(answer) == 0:
        answer = '0'
        
    return answer

11, 12, 13, 14, 15번에서 시간초과가 발생하였다. 

애초에 효율성이 썩 좋을 것 같진 않았어서...예상했음 ^_ㅜ

 

 

문제 풀이 접근법2

1) 생각해보니 counter함수를 사용하면 굳이 for문을 사용하면서 딕셔너리 정의를 하지 않아도 되어서(물론 시간 복잡도는 비슷하겠지만..) 바꾸어주었다.

2) min 역시 직접 구하기 보단 함수로 구할 수 있으므로 코드를 바꾸어 작성했다. 

3) 생각해보니까 max값은 결국 same 리스트를 내림차순으로 정렬한 뒤 문자열로 합치는 거랑 같은거 아닌가? 라는 생각이 들어서 그렇게 바꾸었다. 

4) answer의 경우도 형변환이 아니라 맨 앞자리가 0인지를 확인해보는 것으로 바꾸었다. (내림차순 정렬이므로 앞이 0 == 다 0)

from collections import Counter

def solution(X, Y):
    answer = ''
    same = []
    
    X_dict = Counter(X)
    Y_dict = Counter(Y)
   
    for i in list(X_dict):
        for j in list(Y_dict):
        
            if i == j:
                same.append(i*min(X_dict[i], Y_dict[j]))
                
    if len(same) == 0:
        answer = '-1'
               
    else:
        same.sort(reverse=True)
        answer = ''.join(same)
    

    if answer[0] == '0':
        answer = '0'
        
    return answer

효율성이 썩 좋다고 말할 수는 없지만 통과했다!

순열을 구해서 그 중 max값을 찾는 것 보다(거기에 int로 형변환까지 해야함) 정렬이 훨씬 시간 복잡도가 줄어들 것 같긴하다. 

첫번째 코드에서는 테스트 케이스 6, 7도 2~3000ms까지 걸렸는데 이정도면 낫배드일지도??

 

---