[프로그래머스] 숫자 짝꿍(python)

문제

두 정수 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의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

 입출력 예

 

 

 

 

풀이

 이 문제는 숫자로 이루어진 문자열 2개를 입력받고, 입력받은 두 문자열을 비교하여 공통으로 나타나는 숫자를 찾아내고, 찾아낸 수로 만들 수 있는 가장 큰 정수를 return 하는 문제입니다. 여기서 가장 큰 정수를 만들기 위해서는 공통되는 수를 내림차순으로 정렬한 후 한줄로 출력하면 됩니다. 이를 이용하여 진행한 풀이순서는 다음과 같습니다.

 

1. 이중 for문을 이용하여 X의 i번째 값과 Y의 i 번째 값을 비교 후, 같으면 값을 저장할 리스트에 append 해주고 해당 값을 삭제합니다.

2. 반복문이 모두 수행된 후 결과를 담은 result 리스트의 값을 내림차순으로 정렬합니다.

3. 만약 result의 길이가 0일 경우 '-1'을 리턴해줍니다.

4. 만약 result의 첫번째 값 (result[0]) 이 '0'인 경우 최종적인 값은 0이 되어야 하므로 '0'을 리턴해줍니다.

5. 그 외의 경우 result의 값을 join을 이용하여 출력해줍니다.

 

def solution(X, Y):
    result = []    

    for i in X:
        if(i in Y):
            result.append(i)
            Y = Y.replace(i, '', 1)
    
    result.sort(reverse = True)
    
    if(len(result) ==0):
        return '-1'
    elif(result[0] == '0'):
        return '0'
    else:
        answer = ''.join(result)
    
    return answer

이렇게 코드를 작성 후 테스트를 진행하니 정상적으로 통과하였습니다. 그러나 제출 후 채점을 진행해보니

 

위와 같이 일부 테스트케이스에서 시간 초과가 발생하였습니다....;;

이를 해결하기 위해 블로그 및 질문하기를 참고해보니 X와 Y를 하나하나씩 비교하는 과정에서 시간 초과가 발생할 수 있다는 것을 보았고, 숫자는 0에서 9까지의 범위로 이루어져있다는 힌트를 보고 접근을 새롭게 할 수 있었습니다.

 

먼저 각 문자열에 0-9까지의 숫자가 몇개씩 존재하는지 확인할 수 있는 리스트를 2개 만들어 준 후, 해당 숫자 n이 나오면 리스트의 n번째 값을 1씩 증가시켜주고, 9부터 -1씩 내려오면서 중복되는 개수만큼 출력하면 해결할 수 있습니다. 풀이 방식을 정리하면 다음과 같습니다.

 

1. 각각의 문자열에서 0~9 까지의 숫자가 몇 개 존재하는지 확인할 수 있는 리스트 a,b를 생성합니다.

2. for문을 이용하여 X와 Y에 대해 각각의 숫자가 몇번 나왔는지 카운트 해줍니다.

3. 9부터 0까지 1씩 감소하며 a[i] 와 b[i]의 값을 이용하여 해당 숫자가 몇번 겹치게 되었는지 확인 후, 중복되는 수만큼 결과값에 추가해줍니다.

4. 결과의 길이가 0인 경우, 첫번째 값이 '0'인 경우, 그외의 경우로 나누어 결과값을 출력해줍니다.

 

코드로 구현하면 다음과 같습니다.

def solution(X, Y):
    result = ''
    a = [0,0,0,0,0,0,0,0,0,0]
    b = [0,0,0,0,0,0,0,0,0,0]
    
    for i in X:
        value = int(i)
        a[value] += 1
    
    for i in Y:
        value = int(i)
        b[value] += 1
    
    for i in range(9,-1,-1):
        value = str(i) * min(a[i],b[i])
        result += value
 
    if(len(result) == 0):
        return '-1'
    if(result[0] == '0'):
        return '0'
              
    return result

 

 

위와 같이 풀이를 진행해보니 이전에 통과하지 못했던 일부의 테스트케이스 모두 통과된 것을 확인할 수 있습니다.