[프로그래머스 lv1] 숫자 짝꿍

https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

 

문제설명

 

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

 

문제 해결 방법

 

순회를 통한 문제 해결 

 

 

코드 구현

from collections import deque
def solution(X, Y):
    answer = ''
    
    tem = []
    
    Y=list(Y)
    Y.sort()
    
    X=list(X)
    X.sort()
    
    y = deque(Y)
    
    new = deque()
    cnt = 0
    for idx, i in enumerate(X):
        while 1:
            if cnt == len(y):
                break

            t= y[cnt]
            if i == t:
                del y[cnt]
                tem.append(t)
                break
            else:
                if y[cnt]<i:
                    cnt+=1
                else:
                    break
    
    if len(tem) == 0:
        return '-1'
    else:
        cntt = 0
        check = 0
        while 1:
            if cntt == len(tem):
                break
                
            if check == 1:
                break
            
            if tem[cntt] =='0':
                check = 0
                cntt +=1
            else:
                check =1
                
    if check == 0:
        return "0"
        
    tem.sort(reverse=True)
    answer = "".join(tem)
    
    return answer

 

 

시간/공간 복잡도

 

최악의 경우 O(N)

 

 

최적화 및 개선

 

테스트케이스 11번~ 15번까지 실패했다. 

실패 이유는 시간초과였는데, 문제 조건에서 X, Y는 최대 300만 까지의 길이를 가질 수 있다고 했다. 

 

기존에 내가 작성한 코드는 X를 전부 돌면서 Y또한 전부 순회하도록 돼있었는데, 그러면 시간초과가 날 수 밖에 없는 상황이였다. 즉, 길이가 긴 대상을 전부 순회하지 않고 원하는 값을 찾아야 했다. 

 

한번의 순회로 각 숫자들의 개수를 셀 수 있어야 했다. 

 

어려웠던 점

 

길이가 긴 대상에 대한 고려를 생각해내지 못했다. 

이부분에 대해서 담엔 틀리지 말아야징 ㅎ,,