728x90
반응형
Today I Learned
오늘 팀원들과 코딩테스트 문제를 푸는 중에
팀원분이 흥미로운 코드를 가져오셔서 그것에 대해 공부했다
어떤 문제가 있었는지
# 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 = "100"
Y = "203045"
answer = ''
arr_x = [0]*10
arr_y = [0]*10
for i in X:
arr_x[int(i)]+=1
for i in Y:
arr_y[int(i)]+=1
for i in range(0,10):
answer = str(i)*(min(arr_x[i],arr_y[i])) + answer
if answer == '': answer = '-1'
elif answer.replace('0','') == '': answer = '0'
print(answer)
# 제출용 함수
def solution(X, Y):
answer = ''
arr_x = [0]*10
arr_y = [0]*10
for i in X:
arr_x[int(i)]+=1
for i in Y:
arr_y[int(i)]+=1
for i in range(0,10):
answer = str(i)*(min(arr_x[i],arr_y[i])) + answer
if answer == '': answer = '-1'
elif answer.replace('0','') == '': answer = '0'
return answer나는 그냥 무난하게 풀었다.
기존에 짰던 코드는 시간복잡도가 O(2n^2)여서 자꾸 시간초과가 떴었는데
방식을 바꿔보니 O(2n)으로 줄일 수 있었다. 역시 알고리즘을 어떻게 짜느냐에 따라 큰 차이가 난다.
어떻게 해결 했는지
from collections import Counter
def solution(X, Y):
intersection = list((Counter(X) & Counter(Y)).elements())
intersection.sort(reverse=True)
a = "".join(sorted(intersection, reverse=True))
if set(a) == {"0"}:
return "0"
elif a == "":
return "-1"
else:
return a흥미가 있었던 코드는 바로 collections의 Counter 클래스였다.
Count 클래스는 해시 가능한 객체들의 개수를 세는 데에 사용된다고 한다.
Count 객체를 생성할 때, 리스트나 튜플과 같은 반복 가능한(iterable) 객체를 전달하면,
해당 객체 안에 있는 요소들의 개수를 셀 수 있다.
그리고 Count 객체는 각 요소와 개수를 딕셔너리 형태로 저장한다.
몇가지 자주 쓰이는 메소드들도 찾아봤다.
from collections import Counter
fruits = ['apple', 'banana', 'cherry', 'apple', 'cherry', 'cherry']
fruits_count = Counter(fruits)
# most_common(n=None) : Counter 객체에 저장된 요소들 중
# 가장 빈도가 높은 n개의 요소와 그 개수를 리스트로 반환한다
# 인자 n을 생략하면 모든 요소를 반환한다
most_common_fruits = fruits_count.most_common(2) # 빈도가 가장 높은 2개의 요소 반환
print(most_common_fruits) # 출력: [('cherry', 3), ('apple', 2)]
# elements() : Counter 객체에 저장된 요소들을 반복자(iterator)형태로 반환
# 요소의 개수만큼 요소가 반복된다
elements = list(fruits_count.elements()) # 요소를 반복자에서 리스트로 변환
print(elements) # 출력: ['apple', 'apple', 'banana', 'cherry', 'cherry', 'cherry']
# update(iterable) : Counter 객체에 iterable 객체를 전달하여 요소들의 개수를 업데이트
more_fruits = ['apple', 'mango', 'mango', 'orange']
fruits_count.update(more_fruits) # fruits_count에 more_fruits의 요소들을 추가
print(fruits_count) # 출력: Counter({'cherry': 3, 'apple': 3, 'mango': 2, 'banana': 1, 'orange': 1})
# subtract(iterable) : Counter 객체에서 iterable 객체를 전달하여 요소들을 뺌 (차집합)
fruits1 = ['apple', 'banana', 'cherry', 'apple', 'cherry', 'cherry']
fruits2 = ['apple', 'mango', 'mango', 'orange']
fruits_count1 = Counter(fruits1)
fruits_count2 = Counter(fruits2)
fruits_count1.subtract(fruits_count2) # fruits_count1에서 fruits_count2의 요소들을 뺌
print(fruits_count1) # 출력: Counter({'cherry': 3, 'banana': 1})
무엇을 새롭게 배웠는지
collections의 Counter 클래스와 자주쓰이는 메소드들에 대해 공부했다.
728x90
반응형
