두 수의 짝꿍: 두 정수 X, Y의임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수
단,공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만사용
X, Y의짝꿍이 존재하지 않으면, 짝꿍은-1
X, Y의짝꿍이 0으로만 구성되어 있다면, 짝꿍은0
두 정수 X, Y가 주어졌을 때,X, Y의 짝꿍을 return
ex)
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 한 개는 짝 지을 수 없음)
제한사항
3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000
X, Y는 0으로 시작하지 않음
X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로,문자열로 반환
"""
입출력 예시)
X = "100", Y = "2345" -> "-1"
X = "100", Y = "203045" -> "0"
X = "100", Y = "123450" -> "10"
X = "12321", Y = "42531" -> "321"
X = "5525", Y = "1255" -> "552"
"""
## 의사코드 ##
## X와 Y에서 공통으로 나타나는 숫자 문자열을 구하기##
# Counter()를 활용해서 dict 형태로 X와 Y의 각 원소와 그 원소의 개수를 구함 -> {'숫자 문자열': 개수}
# for 문을 돌면서 dict의 key값인 X의 원소가 Y에도 있고, 그 원소가 각각의 dict에서 값이 0이 아니면(X, Y에서 공통된 정수이면)
# 그 원소를 리스트에 삽입하고, 각각의 dict에서 값 -1 함 (개수 빼주기)
## 공통으로 나타난 숫자 문자열을 담은 리스트에서 permutations로 가장 큰 정수인 짝꿍을 구함##
# -> 이때, 개수는 len(리스트)로 구함 (만들 수 있는 가장 큰 정수를 만들어야 하니까)
# permutations 구하기 -> str 원소 그대로 사용
# from itertools import permutations
# permu = list(permutations(리스트, len(리스트)))
# permu의 각 원소에서 str을 합쳐서 하나의 정수로 만들기 -> "".join()
# 리스트의 str 원소를 int로 변환 -> list(map(int, 리스트))
# max(리스트)로 가장 큰 정수를 뽑아서 str()으로 변환하기
## 짝꿍 반환 ##
# X와 Y의 짝꿍이 0으로만 되어있으면
# return "0"
# X와 Y의 짝꿍이 존재하지 않으면
# return "-1"
# else:
# return 짝꿍
통과한 코드
from collections import Counter
def solution(X, Y):
X_dict = Counter(X)
Y_dict = Counter(Y)
common = [] # 공통으로 나타나는 정수를 담을 리스트
for k in X_dict.keys(): # X에 있는 숫자가
if k in Y_dict.keys(): # Y에도 있으면
while X_dict[k] > 0 and Y_dict[k] > 0: # 그리고 그 숫자가 X와 Y의 dict에서 값이 모두 0보다 크면 (X, Y에서 공통된 정수이면)
common.append(k) # 숫자를 common에 삽입
X_dict[k] -= 1 # X의 dict에서 그 숫자가 나온 횟수 -1
Y_dict[k] -= 1 # Y의 dict에서 그 숫자가 나온 횟수 -1
# 가장 큰 정수를 만들기 위해 큰 수부터 내림차순 정렬
common.sort(reverse=True)
# X와 Y의 짝꿍이 존재하지 않으면
if len(common) == 0:
return "-1"
# X와 Y의 짝꿍이 0으로만 되어있으면
elif common.count("0") == len(common):
return "0"
return ''.join(common) # common의 각 원소를 합쳐서 하나의 정수로 만들기
-> 처음에는 공통으로 나타나는 정수들을 구해서 permutations로 만들 수 있는 수들의 조합을 구한 다음, 가장 큰 정수인 짝꿍을 구하는 것으로 생각했는데
그냥 공통으로 나타나는 정수들을 담은 리스트를 큰 수부터 오도록 내림차순 정렬해서 join() 하면 끝남
X와 Y에서 공통으로 나타나는 숫자 문자열 구하기
-> Counter() 활용
X = "3403"
Y = "13203"
from collections import Counter
X_dict = Counter(X)
Y_dict = Counter(Y)
print('X:', X_dict)
print('Y:', Y_dict, '\n')
common = []
for k in X_dict.keys():
if k in Y_dict.keys():
while X_dict[k] > 0 and Y_dict[k] > 0:
common.append(k)
X_dict[k] -= 1
Y_dict[k] -= 1
print('common:', common)
print('남은 X:', X_dict)
print('남은 Y:', Y_dict)
"""
X: Counter({'3': 2, '4': 1, '0': 1})
Y: Counter({'3': 2, '1': 1, '2': 1, '0': 1})
common: ['3', '3', '0']
남은 X: Counter({'4': 1, '3': 0, '0': 0})
남은 Y: Counter({'1': 1, '2': 1, '3': 0, '0': 0})
"""
cf) 리스트의 원소가 문자열일 때 정렬하기
li = ['303', '330', '033', '033', '330', '303', '40']
li.sort()
li
"""
['033', '033', '303', '303', '330', '330', '40']
"""
-> 문자열인 상태에서 정렬하면 일단 맨 앞자리 수부터 비교함 ('330'보다 '40'이 더 큰 것으로 간주)
