[프로그래머스] 숫자 짝꿍

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/131128

 

프로그래머스

 

---

문제 풀이

from collections import Counter

def solution(X, Y):
    # 각 숫자의 빈도를 계산
    count_x = Counter(X)
    count_y = Counter(Y)
    
    # 공통 숫자와 빈도를 저장할 리스트
    common_digits = []
    
    # 공통 숫자를 빈도에 맞게 추가
    for digit in count_x:
        if digit in count_y:
            common_digits.extend([digit] * min(count_x[digit], count_y[digit]))
    
    # 가장 큰 수로 배열하기
    common_digits.sort(reverse=True)
    
    # 결과가 0으로만 구성된 경우 0 반환
    if common_digits and common_digits[0] == '0':
        return '0'

    
    # 공통 숫자가 없는 경우 -1 반환
    if not common_digits:
        return '-1'
    
    # 공통 숫자로 가장 큰 수를 생성하여 반환
    return ''.join(common_digits)

 

사실 문제 자체는 어렵지 않았지만, 시간 복잡도를 줄이느라 고민을 좀 했다.

 

---

extend 메서드

리스트에 다른 iterable(예: 리스트, 튜플, 문자열 등)의 모든 요소를 추가하는 데 사용한다.

 

 

예제

 

1. 리스트에 리스트 추가하기

fruits = ['apple', 'banana']
more_fruits = ['orange', 'mango']
fruits.extend(more_fruits)
print(fruits)  # 출력: ['apple', 'banana', 'orange', 'mango']

 

2. 리스트에 문자열 추가하기

numbers = [1, 2, 3]
additional_numbers = '456'
numbers.extend(additional_numbers)
print(numbers)  # 출력: [1, 2, 3, '4', '5', '6']

 

3. 리스트에 튜플 추가하기

items = [1, 2, 3]
more_items = (4, 5)
items.extend(more_items)
print(items)  # 출력: [1, 2, 3, 4, 5]

 

---

append vs extend

append

fruits = ['apple', 'banana']
fruits.append(['orange', 'mango'])
print(fruits)  # 출력: ['apple', 'banana', ['orange', 'mango']]

 

extend

fruits = ['apple', 'banana']
fruits.extend(['orange', 'mango'])
print(fruits)  # 출력: ['apple', 'banana', 'orange', 'mango']

---

공통된 숫자를 찾는 다양한 방법

 

1. 빈도 수를 이용하는 방법

from collections import Counter

def find_common_digits_with_frequency(X, Y):
    count_x = Counter(X)
    count_y = Counter(Y)
    common_digits = []
    for digit in count_x:
        if digit in count_y:
            common_digits.extend([digit] * min(count_x[digit], count_y[digit]))
    return common_digits

내가 사용한 방법.

 

공간, 시간복잡도를 가장 효율적으로 사용하는 성능이 좋은 방법이다.

---

2. set를 사용하는 방법

def find_common_digits(X, Y):
    set_x = set(X)
    set_y = set(Y)
    common_digits = set_x.intersection(set_y)
    return list(common_digits)

---

3. 리스트 탐색을 통한 방법

def find_common_digits_by_search(X, Y):
    list_x = list(X)
    list_y = list(Y)
    common_digits = []
    for digit in list_x:
        if digit in list_y:
            common_digits.append(digit)
            list_y.remove(digit)  # 중복되지 않도록 제거
    return common_digits

remove() 는 최악의 경우 O(n)의 시간 복잡도를 가지므로,

입력 데이터가 커지면 전체 시간 복잡도가 크게 증가할 수 있어 비효율적이다.

---

다른 풀이

 

def solution(X, Y):
    answer = ''

    for i in range(9,-1,-1) :
        answer += (str(i) * min(X.count(str(i)), Y.count(str(i))))

    if answer == '' :
        return '-1'
    elif len(answer) == answer.count('0'):
        return '0'
    else :
        return answer

미쳤다...! 잠이 확깨네

digit의 경우는 0~9 의 10가지이므로, for문으로 9부터 -1까지 10번만 도는 것이다.

 

그리고 나처럼 sort()로 정렬을 위해 list를 사용한 게 아닌,

문자열에 바로 추가를 해주었다.

반복문이 가장 큰 digit 9부터 순서대로 도므로, 자연히 큰 수부터 문자열에 추가되는 것이다. 소름..!

 

count() 메소드

 

문자열(str)과 리스트(list) 객체에서 사용할 수 있다.

문자열에서 특정 서브 문자열(부분 문자열)이 몇 번 발생하는지 세는 메서드라고 한다.

text = "hello hello hello"
print(text.count("hello"))  # 출력: 3
print(text.count("o"))      # 출력: 4

---

from functools import reduce
import re
def solution(X, Y):
    result = "".join(sorted(reduce(lambda result, i: result + i*min(X.count(i), Y.count(i)), map(str, range(10)), ""), reverse=True)) or "-1"
    return "0" if re.match(r"0+", result) else result

한줄로 되긴 되는데... 가독성 떨어져서 좀 징그럽다.

 

---