프로그래머스 | 숫자 짝꿍 (파이썬) SET 교집합

 

오늘도 오랑이는 문제를 풉니다.

 

숫자 짝꿍

 

 

풀이 과정 1

• X 와 Y 의 각 숫자 비교, 일치할 경우 temp 리스트에 넣어주기 
• 각각의 케이스 정의 (-1, 0, 내림차순 정렬 숫자)

이때 첫 번째 조건에서 아래와 같은 예시에 있어 5가 3개 들어가는 것을 방지하기 위해 일치할 경우 Y의 숫자를 공백으로 대체해줍니다. 

다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)

def solution(X, Y):
    answer = ''
    temp = []
    
    for i in X:
        if i in Y:
            temp.append(i)
            Y = Y.replace(i,"",1)
    
    temp.sort(reverse=True)
    answer = ''.join(temp)
    if not temp:
        return '-1'
    if temp.count('0') == len(temp):
        return '0'
    
    return answer

 

하지만 위 풀이로는 시간 초과 문제가 발생해서 테스트를 통과하지 못했습니다. 

아마 X, Y 가 길 경우 하나하나 대조하는 for문에서 너무 오래 걸려서인듯 합니다. 

 

 

풀이 과정 2

다른 풀이를 참고해보았습니다.

뒷 부분은 동일해서 설명을 생략하고, 앞에 for문을 대체해줄 코드를 입력 예시와 함께 살펴봅시다. 

X = "5525" Y = "1255"

for i in (set(X)&set(Y)) :
    for j in range(min(X.count(i), Y.count(i))) :
        answer.append(i)

 

전에 본 SET 함수로 각각 X, Y 에 대해 중복제거 작업을 해준 후 교집합으로 짝이 될 수 있는 숫자들을 추려줍니다.

set(X) = 5, 2, set(Y) = 1, 2, 5
→ 둘의 교집합은 2, 5

 

두번째 for 문은 i를 짝이 이루어질 수 있는 개수만큼 반복해주기 위한 문구인데요

각 X와 Y 에 공통 숫자가 몇 개씩 들어가 있는지 count 해주고, 그 중 최솟값만큼 i를 answer 에 넣어줍니다. 

X.count(i) = 3, Y.count(i) = 2 → min = 2
숫자 5에 대해 for문 2번 반복해 answer 에 5 2개 넣어주기

 

하지만 여기서 for 문으로 count를 수행하는 방식은 덜 직관적이고 효율성이 떨어지는데요,

더 좋은 방법은 반복문 없이 바로 최솟값만큼 문자열 i 를 곱해주는 것입니다. 

for i in (set(X)&set(Y)) :
    answer += [i] * min(X.count(i), Y.count(i))

 

 

최종 코드

def solution(X, Y):
    answer = [] 
    
    for i in (set(X)&set(Y)) :
        answer += [i] * min(X.count(i), Y.count(i))
            
    answer.sort(reverse=True)
    if not answer:
        return "-1"
    if answer[0] == "0":
        return "0"
    answer = "".join(answer)
    return answer

 

 

 

 

오랑우탄이 영어를 하고 오랑이가 코드마스터가 되는 그날까지~

 

 

 

프로그래머스