[프로그래머스 / 파이썬] Lv.1 숫자 짝꿍

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

 

제한 사항

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

입출력 예

X	Y	result
"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

 

 

소스 코드

# 1 (시간 초과)
def solution(X, Y):
    answer = ""

    inter = []

    for x in X:
        if x in Y:
            inter.append(int(x))
            Y = Y.replace(x,"",1)  

    inter.sort(reverse=True) 
    if len(inter) == 0:
        answer = "-1"
    elif inter[0] == 0:
        answer = "0"
    else:
        for i in inter:
            answer += str(i)
        
    return answer

 

풀이 # 1

• 교집합 원소를 담을 inter 리스트 생성
• X를 돌면서 X의 원소가 Y에 있으면 inter 리스트에 해당 원소 추가하고 Y에서 해당 원소 삭제
  • replace("바꾸기 전 문자", "바꾼 후의 문자", 바꾸고 싶은 문자 갯수)
• inter 를 내림차순으로 정렬
• inter가 없을 경우 "-1", 0이 여러개인 경우에는 "0"을 출력
• inter가 있고 0이 아니라면 리스트를 돌면서 문자를 answer에 추가

 

# 2
def solution(X, Y):
    answer = ""

    numberX = [0]*10
    numberY = [0]*10
    
    # 각 숫자가 몇 개씩 있는지 카운트
    for x in X:
        numberX[int(x)] += 1
    
    for y in Y:
        numberY[int(y)] += 1


    # 반복문을 돌면서 추가
    for idx in range(9,-1,-1):
        if numberX[idx] > 0 and numberY[idx] > 0:
            cnt = min(numberX[idx], numberY[idx])
            answer += (str(idx) * cnt)

    if answer == "":
        answer = "-1"
    elif answer[0] == "0":
        answer = "0"

        
    return answer

 

풀이 #2

• X와 Y의 각 숫자 갯수를 numberX와 numberY에 카운트 (각 숫자 = 인덱스)
• sort를 하지 않기 위해 가장 큰 수부터 반복문
  • numberX와 numberY에 둘 다 존재하면 둘 중에 작은 수만큼 answer에 추가
• 교집합이 없거나 0이 여러 개인 경우 처리

 

 

문제 자체는 단순한데 제한 사항을 보면 정수가 상당히 클 수도 있다는 조건이 있다. sort를 이용하면 시간이 오래 걸리므로 sort를 사용하지 않고 for문도 10개 숫자 내에서 돌도록 코드를 수정하였다. 통과는 했지만 시간이 적게 걸리는 것 같지는 않다. 시간 복잡도도 고려해서 코드를 짜는 게 중요한데....어렵구만...