[파이썬] 숫자 찾기

Contents

문제

내용

• 내가 짠 코드는 였고 테스트케이스 11~15번이 시간초과가 떴음

def solution(X, Y):
    answer = ''
    # 정수 X, Y 임의의 자리에서 공통으로 나타나는 정수 k (0 <= k <= 9)
    # k들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 한다.
    
    # 짝꿍이 없다면 -1이며, 짝꿍이 모두 0이면 0이다.
    
    # input, output 모두 string이다. 자료형에 유의할 것
    
    twins = []
    X_list = [x for x in X]
    Y_list = [y for y in Y]
    
    for x in range(len(X_list)):
        for y in range(len(Y_list)):
            if X_list[x] == Y_list[y]:
                twins.append(Y_list.pop(y))
                break
    
    if len(twins) == 0:
        return '-1'
    
    twins = list(map(lambda n: int(n), twins))
    
    twins.sort(reverse=True)
    
    if len(twins) > 1 and twins[0] == 0:
        return '0'
    
    return ''.join(list(map(lambda n: str(n), twins)))

• 정답 코드를 보니 다음과 같은 방법으로 쉽게 해결할 수 있음을 알 수 있었다.
1. BigInteger는 자릿수로 판별해야 한다. 따라서 두 BigInteger 사이에 0~9의 개수를 비교하여 작은 쪽이 숫자 짝꿍이 된다.
2. 0~9의 개수를 모두 파악했다면, 리스트 축약을 활용해 문자열로 정답을 변환한 후 반환한다.

• 다시 작성한 코드
의 시간복잡도가 나왔다.
문자열에서 제공하는 내장 함수인 count()를 사용하여 특정 문자의 개수를 찾고, 이를 다른 문자열에도 동일하게 적용해 두 문자열 사이의 개수 중 작은 쪽을 선택한다.
이렇게 하여 보다 더 pythonic하면서도 시간복잡도가 적은 코드를 구현할 수 있다.

def solution(X, Y):
    answer = ''
    num_count = [0 for i in range(10)]
    
    for i in range(9, -1, -1):
        num_count[i] = min(X.count(f'{i}'), Y.count(f'{i}'))
        answer += ''.join([f'{i}' for j in range(num_count[i])])
        
    if answer == '':
        return '-1'
    elif len(answer) > 1 and answer[0] == '0':
        return '0'
    else:
        return answer