[프로그래머스 Lv.1] 숫자 짝꿍(Python)

코딩테스트 연습 - 숫자 짝꿍 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제

두 정수 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

 

 

 

---

풀이

 

아이디어 :
replace를 이용하면 길이가 길어질수록 매우 비효율적이어서, 시간 복잡도가 높아지며 시간초과가 발생한다. 그래서 Counter 클래스를 사용해 주었다. Counter 함수는 문자열을 한 번씩만 순회하면서 카운트를 계산하므로, 시간 복잡도를 크게 줄일 수 있다.

X와 Y에서 각 숫자가 몇 번 나타나는지 세고, 공통된 숫자를 찾는다. 공통된 숫자에서 횟수는 X와 Y 중 더 적게 나타난 횟수를 기준으로 한다. 공통된 숫자를 찾을때는 9부터 0까지 순서대로 진행하여 자동으로 큰 수로 정렬되도록 만든다. 만약 결과의 첫번째 원소가 0이라면 이전에 0 이상의 큰 수는 공통되지 않았다는 뜻이므로 이때는 0을 반환하도록 한다.  

 

from collections import Counter

def solution(X, Y):
    # X와 Y의 각 숫자의 개수를 센다.
    count_X = Counter(X)
    count_Y = Counter(Y)
    
    result = []   
    # 0부터 9까지 숫자에 대해 공통된 숫자를 찾는다. 
    # 큰 숫자부터 작은 숫자로 순회하여 가장 큰 수를 바로 찾을 수 있다.
    for num in "9876543210":
        if num in count_X and num in count_Y:  # 두 문자열에 모두 있는 숫자를 찾는다.
           # 공통된 숫자를 결과에 추가 (X와Y 중 개수가 적은 수만큼 반복이 가능)
            result.append(num * min(count_X[num], count_Y[num]))
    
    # 결과가 비어 있으면 -1을 반환 (result가 비어있다면 False 이므로 not을 조건으로 붙여준다.)
    if not result:
        return '-1'
    
    # 모든 숫자가 0이면 0을 반환
    # 합쳐진 문자열의 첫 번째 문자가 '0'이면, 이는 모든 문자가 '0'이었음을 의미한다.
    result_str = ''.join(result)
    if result_str[0] == '0':
        return '0'
    
    return result_str

 

 

Counter 클래스

Counter 함수는 객체의 빈도를 계산하는 데 사용된다.
Counter는 주어진 iterable(리스트, 문자열 등)의 각 요소가 몇 번 등장했는지를 세고, 이를 딕셔너리 형태로 저장한다.

ex) Counter("112233")를 사용하면 {'1': 2, '2': 2, '3': 2}와 같은 딕셔너리가 생성된다.

 

 

 

 

처음 풀이 (오답)

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

 

처음에는 X의 원소를 순회하면서 해당 원소가 Y에 있다면 그 숫자를 replace를 이용하여 삭제하면서 리스트에 추가하는 방식으로 풀었다. 하지만 이 풀이는 X의 원소 개수만큼 Y를 순회해야 해서 숫자가 꽤 클때는 시간 초과 에러를 발생시킨다.

 

 

 

replace() 의 count 파라미터

X.replace('a','b')는 기본적으로 X의 모든 a를 b로 바꾼다.
이때 count 파라미터를 사용하면 변경할 횟수를 지정해 줄 수 있다.
( 하지만 replace는 keywords arguments를 받지 않으므로 그냥 숫자만 넣어줘야 한다.)

예를들어 X.replace('a','b',2) 이런식으로 횟수를 지정해 준다면 X에서 2번째 a까지만 b로 바꾼다.

 

 

 

 

all() vs any()

 

all()
all() 함수는 파이썬 내장 함수 중 하나로, 주어진 iterable(리스트, 튜플, 문자열 등)의
모든 요소가 참(True)인지 확인한다.

all() 함수는 iterable의 모든 요소가 True로 평가되면 True를 반환.

만약 iterable에 False가 하나라도 있다면 False를 반환.

 

 

any()
주어진 iterable(리스트, 튜플, 문자열 등)의 요소의 True/False를 확인한다.
any() 함수는 이 중 하나라도 참이면 True를 반환.