[프로그래머스] 숫자 짝꿍 (파이썬, 시간복잡도 개선)

내 풀이가 나름 마음에 들어서 기록해본다.

 

[문제]

 

 

[코드]

def solution(X, Y):

	# X_lst, Y_lst: X, Y 숫자세기용 리스트 / lst: 겹치는 숫자세기용 리스트
    X_lst, Y_lst, lst = [0] * 10, [0] * 10, []
    
    # X, Y에 있는 숫자들의 개수 세줌
    for i in X:
        X_lst[int(i)] += 1
    for i in Y:
        Y_lst[int(i)] += 1
        
    # 특정 숫자가 X, Y에 모두 들어있으면 둘 중에 적은 개수만큼 lst에 저장해줌(e.g. 55, 2)
    for i in range(10):
        if X_lst[i] != 0 and Y_lst[i] != 0:
            lst.append(str(i) * min(X_lst[i], Y_lst[i]))
            
    # 가장 큰 수를 찾아야 하므로 reverse해서 내림차순 정렬함
    lst.sort(reverse=True)
    
    # 출력값에 따라서 return함
    # 겹치는 숫자가 있고,
    if len(lst) != 0:
    	# 겹치는 숫자가 0만 있는 게 아니라면 lst값을 모두 붙여서 출력
        if int(lst[0]) != 0:
            return ''.join(lst)
        # 겹치는 숫자가 0밖에 없다면 '0' 출력
        else:
            return '0'
    # 겹치는 숫자가 없으면 '-1' 출력
    else: 
        return '-1'

 

 

[아쉬운 점]

sort 대신 위에서 range(9,1,-1)로 넣었으면 시간복잡도 $O(N+M+k\log k)$을 $O(N+M)$로 줄일 수 있었을 것이다.

 

 

[느낀점]

경우의 수 하나하나 생각하면서 차분하게 코드 짜면 된다!