(프로그래머스) 42. 삼총사

코드 작성 및 풀이

1. 개선 후

from itertools import * # 내장함수 사용

def solution(number):
    cnt = 0
    CombList = list(combinations(number, 3))
    for i in range(len(CombList)):
        if sum(CombList[i]) == 0: # 변수 할당하지 않고 튜플 값 자체를 sum()으로 더해서 비교
            cnt += 1
    return cnt

 

2. 개선 전

변수 할당을 최소화 하기 위해 개선함 (test는 불필요한 변수)

from itertools import * # 내장함수 사용

def solution(number):
    test = 0
    cnt = 0
    CombList = list(combinations(number, 3)) # 중복없는 조합 Tuple로 생성
    for i in range(len(CombList)):
        for j in range(len(CombList[i])):
            test += CombList[i][j] # 테스트 변수에 튜플 내 값을 모두 더해봄

        if test == 0: # 튜플의 합이 0인 경우 count 1
            cnt += 1
            test = 0
        else: # 튜플의 합이 0이 아닌 경우
            test = 0

    return cnt

시간 복잡도 : O(nCr)

Combination이 중첩 반복문보다 시간 복잡도가 높으므로 Combination을 따라감
Combination : O(nCr)
n = number, r = 3개 조합
n개의 원소에서 3개를 선택하는 조합의 개수
중첩 반복문 : O(N^2)

과정

- 내장 함수를 사용해도 되는지에 대해 고민이 들었으나, 어떤 시간 복잡도로 처리되는지를 알면 효율적으로 사용할 수 있을듯
- 예전에 내가 정리해둔 자료를 참고했다. 기록은 힘!
https://armontad-1202.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%AA%A8%EB%93%A0-%EA%B2%BD%EC%9A%B0%EC%9D%98-%EC%88%98-%EC%B6%94%EC%B6%9C-%EA%B0%80%EB%8A%A5%ED%95%9C-%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9F%AC%EB%A6%AC

파이썬) 모든 경우의 수 추출 가능한 라이브러리

- 3개 중첩 반복문으로도 풀 수 있으나 O(N^3)와 O(nCr)의 복잡도에 큰 차이가 없다고 해서 combination으로 풀었습니다

 

그럼 모두 해피코딩 하세요~!!