[파이썬] 프로그래머스 Lv1. 삼총사

프로그래머스 삼총사.. 푸는데 너무 복잡하게 생각해서 시간도 너무 쓰고 문제를 다 맞추지도 못함..🥲 이 레벨에서 시간이 너무 오래걸리고 조건문을 너무 자주 쓰게 된다면 잘못 되어 가고 있다는 걸로 이해해도 될듯 하다. 어쨌든 조건을 너무 잘게 쪼개서 그 사이 사이로 빠져나간 값들이 많은 것으로 예상됨..

이 문제는 정수 3개씩 그룹으로 묶어서 그 합이 0일 경우를 카운트 해서 리턴하면 된다.

즉 조합을 사용하라는 건데...
조합은 python itertools에서 제공이 된다.
총 3가지 이터레이터(무한 이터레이터, 가장 짧은 입력 시퀀스에서 종료되는 이터레이터, 조합형 이터레이터)가 소개되었는데, 그중 조합형 이터레이터에 컴비네이션이 있다.

<조합형 이터레이터>

• product()
  중첩된 for 룹과 같다. 중복이 허용됨. 아래와 같이 range(2)에서 이진법 만들 때 써도 될 것 같다

  from itertools import product
  
  arr =[]
  for x in product(range(2),repeat=3):
      arr.append(x)
  print(arr)
  # 2 * 2 * 2 = 8개
  # [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), 
  # (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
  
  arr =[]
  for x in product('ABC',repeat=2):
    arr.append(x)
  print(arr)
  # 3 * 3 = 9개
  # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), 
  # ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), 
  # ('C', 'C')]

• permutations()
  중복없이 뽑히는 순서가 상관있을 때
  permutations(재료를 , 몇개씩 넣을까?)

  from itertools import permutations
  arr =[]
  for x in permutations('ABC', 2):
      arr.append(x)
  print(arr)
  # 3! = 3 * 2 = 6개
  # [('A', 'B'), ('A', 'C'), ('B', 'A'), 
  # ('B', 'C'), ('C', 'A'), ('C', 'B')]

• combinations()
  반복 없이 뽑히는 순서가 상관 없을 때

  from itertools import combinations

  arr =[]
  for x in combinations('ABC',2):
    arr.append(x)
  print(arr)
  # 3!/(2! * 1!) = 3개
  # [('A', 'B'), ('A', 'C'), ('B', 'C')]

• combinations_with_replacement()
  똑같은 것이 뽑혀도 되지만 순서가 상관 없을 때
  combinations_with_replacement(k,n)에서 나오는 가짓수는
  (k+n-1)! / (k! * (n-1)!)

  from itertools import combinations_with_replacement
  arr =[]
  for x in combinations_with_replacement('ABC', 2):
    arr.append(x)
  print(arr)
  # (2+3-1)! /(2!*(3-1)!) = 6개
  # [('A', 'A'), ('A', 'B'), ('A', 'C'), 
  # ('B', 'B'), ('B', 'C'), ('C', 'C')]
  
  from itertools import combinations_with_replacement
  arr =[]
  for x in combinations_with_replacement(range(2), 3):
    arr.append(x)
  print(arr)
  # (3+2-1)! / (3!*(2-1)!) = 4개
  # [(0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1)]

<프로그래머스 다른 풀이>

from itertools import combinations

def solution (number) :
    from itertools import combinations
    cnt = 0
    for i in combinations(number,3) :
        if sum(i) == 0 :
            cnt += 1
    return cnt
    
from itertools import combinations
def solution(number):
    return sum(not sum(c) for c in combinations(number, 3))

첫번째 코드의 경우 combination 쌍을 모두 찾아서 그 합이 0이 될 때만 카운트 해서 리턴
두번째 코드의 경우not을 붙여서 sum()이 0이 되는 경우:True를 모두 세서 리턴한다.

nested for loops

def solution(number):
    answer = 0
    l = len(number)
    for i in range(l-2):
        for j in range(i+1, l-1):
            for k in range(j+1, l):
                if number[i]+number[j]+number[k] == 0:
                    answer += 1           
    return answer

직접 조합쌍을 만드는 for-loop을 만들어서 그 합이 0이 되는 경우만 카운트 해서 리턴

성능

		    itertools               nested for-loops
테스트 01 〉	통과 (0.05ms, 10.2MB)	통과 (0.09ms, 10.2MB)
테스트 02 〉	통과 (0.01ms, 10.2MB)	통과 (0.01ms, 10.1MB)
테스트 03 〉	통과 (0.01ms, 10.1MB)	통과 (0.02ms, 10.2MB)
테스트 04 〉	통과 (0.02ms, 10.2MB)	통과 (0.03ms, 10.2MB)
테스트 05 〉	통과 (0.03ms, 10.1MB)	통과 (0.04ms, 10.1MB)
테스트 06 〉	통과 (0.04ms, 10.1MB)	통과 (0.05ms, 10.3MB)
테스트 07 〉	통과 (0.05ms, 10.3MB)	통과 (0.05ms, 10.2MB)
테스트 08 〉	통과 (0.09ms, 10.2MB)	통과 (0.05ms, 10.1MB)
테스트 09 〉	통과 (0.10ms, 10.3MB)	통과 (0.05ms, 10.3MB)
테스트 10 〉	통과 (0.09ms, 10.2MB)	통과 (0.05ms, 10.3MB)
테스트 11 〉	통과 (0.04ms, 10MB)	    통과 (0.06ms, 10.2MB)
테스트 12 〉	통과 (0.04ms, 10.2MB)	통과 (0.06ms, 10.2MB)
테스트 13 〉	통과 (0.05ms, 10.2MB)	통과 (0.03ms, 10.1MB)