240722 TIL

1. 파이썬 combination 구현하기

👉문제 바로 가기

문제를 어떻게 접근해야 할지 고민을 해봤다.

처음에는 중첩 for 문을 사용하려 했으나 인자의 크기가 가변적이라 사용할 수 없게 되었다.

구글링을 했는데 파이썬 itertools.combinations 함수를 사용해서 조합을 쉽게 구할 수 있었다.

그러나 단순히 라이브러리를 활용하는 것에 그치지 않고, 모듈 없이 직접 구현하는 방법을 고려해 보았다.

1) 모듈 사용

from itertools import combinations

def solution(nums):
    answer = 0
    for i in combinations(nums, 3):
        if is_prime(sum(i)):
            answer += 1
    return answer

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

2) 모듈 미사용

def solution(nums):
    answer = 0
    for i in combinations(nums, 3):
        if is_prime(sum(i)):
            answer += 1
    return answer

def combinations(nums, length):
    combos = []
    if length > len(nums):
        return combos
    elif length == 1:
        return  [[num] for num in nums] #nums 와 같지만 포맷 맞추기 위해서
    else:
        for i in range(len(nums) - length + 1):
            first = nums[i]
            rest = nums[i+1:]
            for combo in combinations(rest, length - 1):
                combos.append([first] + combo)
    return combos

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

참고로 is_prime에서 int(num**0.5) + 1까지만 검사한다. 시간초과 방지용이다.

수학적으로 이 범위까지만 확인해도 소수 여부를 결정할 수 있다고 한다.

 

2. 백준 허브

팀원의 소개로 '백준허브'라는 익스텐션을 알게 되었다.

지인의 깃허브에 백준 허브 양식으로 뭔가 계속 커밋되길래 그런게 있나보다 했는데,

직접 써보니 편한것 같다. 그렇지만 지금까지 푼 알고리즘 문제는 집계되지 않는다는게 조금 아쉬웠다.