두 정수 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 함수를 완성해주세요.
제한 사항 1. 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다. 2. X, Y는 0으로 시작하지 않습니다. 3. X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
문자열로 이루어진 숫자에서 공통 값을 추출하는 과정에서 시간 초과가 나지 않도록 효율적인 방법을 찾아야 합니다. 단순 정렬로 풀이하게 된다면 시간 복잡도가 O(n)인 remove 함수로 인해 반복문 내에서 시간초과가 발생합니다.
리스트에서 공통 값을 추출하는 방법으로 Counter를 활용하는 방법이 있습니다. Counter 함수 사용법을 잘 알지 못하여 다음과 같이 정리해보았습니다.
Counter 객체 간 합집합(+), 교집합(&), 차집합(-) 연산을 수행할 수 있는 특징을 이용하게 되면, 두 입력값에서 공통 값과 그 횟수까지 알 수 있습니다.
이후 문제 해결 과정은 다음과 같습니다.
짝꿍이 없을 경우, 0만 나올 경우 예외 값을 리턴해줍니다.
문자열 곱 연산의 특성을 이용해 Counter 함수로 Key 값과 Key값에 저장된 횟수를 곱해 저장합니다.
역순으로 가장 큰 값을 만든 후 리턴해 줍니다.
이렇게 Counter 함수를 사용해서 공통 값과 해당 값이 나온 횟수를 추출할 수도 있지만 defaultdict로 X와 Y의 key, value를 순회하며 직접 리스트를 만들어 풀 수도 있습니다. 혹은 set 함수로 공통으로 나타나는 숫자만 저장할 수도 있습니다.
큰 정수를 뽑아내는 방식도 sort 함수의 reverse 기능을 사용하는 방법을 생각했었지만, 반복문을 주어진 0-9 숫자를 역순으로 순회하여 구하는 방법도 있었습니다.
풀이 방법은 원하는 방식을 선택하면 되지만 그 중 시간 복잡도에 가장 효율적인 방법을 생각할 수 있어야 합니다.
💡 내가 해결한 방식은?
단순 정렬을 이용한 풀이 (시간 초과)
def solution_1(X, Y):
answer = []
y_list = []
tmp = 0
# 중복 제외 값 추출 어떻게?
# 숫자로 이루어진 문자열 특정 인덱스 숫자 값 어떻게 지우지?
# 결국에는 짝꿍이 되면 해당 값 지워주어야 함
# Y 리스트 분해 필수
# Y 값 분해
for idx in list(Y):
y_list.append(idx)
# X와 Y 값 비교
for word in X:
# Y에 해당 숫자가 있을 경우
if word in y_list:
# 해당 숫자 추가
answer += word
# Y에서 해당 숫자 제거
y_list.remove(word)
# 짝꿍이 없을 경우
if len(answer) == 0:
return "-1"
# 0 만 있을 경우
tmp = sum([int(idx) for idx in answer])
if tmp == 0:
return "0"
answer = sorted(answer, reverse=True)
answer = ''.join(answer)
return answer
Counter 함수를 활용한 풀이
from collections import Counter
def solution_2(X, Y):
answer = ''
# Counter 함수를 통해 문자열 안에 포함된 원소의 개수 구하기
# & 연산자로 교집합 구하기
pair_num = Counter(X) & Counter(Y)
# 예외 처리
if not pair_num: # pair_num 에 공통 값이 없는 경우
return '-1'
elif list(pair_num) == ['0']: # 공통 값이 0만 있는 경우
return '0'
# 역순으로 정렬
reverse_num = sorted(pair_num, reverse=True)
# 문자열 곱을 활용한 정답 도출
for num in reverse_num:
answer += num * pair_num[num]
return answer
defaultdict를 사용한 풀이
from collections import defaultdict
def solution(X, Y):
answer = []
# defaultdict value 타입을 int로 초기화
s1 = defaultdict(int)
s2 = defaultdict(int)
# defaultdict를 사용해 각 숫자가 나온 횟수를 저장합니다.
for s in X:
s1[s] += 1
for s in Y:
s2[s] += 1
# 역순으로 반복하여 큰 숫자부터 처리해 짝꿍을 만들어줍니다.
# 그래야 가장 큰 정수를 구할 수 있습니다.
for i in range(9, -1, -1):
# 공통으로 나타나는 숫자의 개수만큼 짝꿍으로 사용할 수 있으므로
# s1, s2 해당 숫자의 개수 중 작은 값을 구합니다.
for j in range(min(s1[str(i)], s2[str(i)])):
# 해당 숫자만큼 반복하여 숫자를 추가합니다.
answer.append(str(i))
# 예외 처리
if not answer:
return '-1'
if answer[0] == '0':
return '0'
return ''.join(answer)
set 함수를 통한 풀이
def solution(X, Y):
answer = ''
crossXY = set(X) & set(Y)
if(len(crossXY) == 0):
return "-1"
elif(len(crossXY) == 1 and '0' in crossXY):
return "0"
l_XY = list(crossXY)
l_XY = sorted(l_XY, reverse=True)
for i in range(len(l_XY)):
minC = min(X.count(l_XY[i]), Y.count(l_XY[i]))
for _ in range(minC):
answer += l_XY[i]
return answer
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
예를 들어,
5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places 가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한 사항 1. places의 행 길이(대기실 개수) = 5 1-1. places의 각 행은 하나의 대기실 구조를 나타냅니다. 2. places의 열 길이(대기실 세로 길이) = 5 3. places의 원소는 P,O,X로 이루어진 문자열입니다. 3-1. places 원소의 길이(대기실 가로 길이) = 5 3-2. P는 응시자가 앉아있는 자리를 의미합니다. 3-3. O는 빈 테이블을 의미합니다. 3-4. X는 파티션을 의미합니다. 4. 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다. 5. return 값 형식 5-1. 1차원 정수 배열에 5개의 원소를 담아서 return 합니다. 5-2. places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다. 5-3. 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.
