문제

number 길이 만큼의 학생이 있고, 각각 정수 번호를 가지고 있을 때 합쳐서 0이 되는 조합의 개수를 찾기

문제링크

나의 문제 접근

1) 가능한 학생 조합을 모두 찾는다
2) 각 조합의 원소가 합쳐서 0이 되는 지 조사한다

이 문제의 핵심은 가능한 학생 조합을 얼마나 효율적으로 찾는가 이다.

나의 풀이

가능한 모든 경우의 수의 예시를 먼저 적어 보고 거기에서 패턴을 찾았다.

1) 첫 번째 숫자(i)는 0 부터 len(number) - 2 까지 반복됨

2) 두 번째 숫자는(j) i+1 부터 len(number) - 1 까지 반복됨

이 때 i+1 부터 반복되는 이유는 i = 0 일 때는 i + 1 인 2 부터 i = 1 일 때는 i + 1 인 3부터 반복되기 때문

3) 세 번째 숫자는(z) j + 1 부터 len(number) 까지 반복됨

여기서도 두번째 경우와 비슷한 이유

len(number) == 5 인 경우를 기준으로 나열한 뒤 패턴을 찾았다.

더 효율적인 풀이

코테 문제를 풀고 나서는 다른 사람들의 풀이를 분석해보는데, 여기에서 더 효율적인 풀이로 combination이라는 라이브러리를 사용하는 방법이 있다는 걸 알게 되었다.

내가 푼 풀이가 범인의 풀이로 대부분이 이렇게 풀었더라. 반면 더 짧고 효율적이고 또 pythonic하게 푼 풀이는 고수의 풀이로, 고수의 풀이를 분석하다 보면 나도 고수의 풀이를 할 수 있지 않을까하는 마음으로 고수의 풀이를 분석해본다.

itertools의 combition, permutation, prodcut 모듈

combinations

우리가 수학시간에 배웠던 combination(조합)이 iteration형태로 나온다.
아래는 iteration형태로 나오는 것을 리스트에 담아준 것.

예를 들어 원소가 5개인 combinations(list_a, 3)은 5C3의 조합, combinations(list_a, 2)는 5C2의 조합

조합은 중복을 배제한다.

from itertools import combination

items = [1, 2, 3, 4, 5]

list(combinations(items, 3))

""" 
 result:
 [(1, 2, 3),
 (1, 2, 4),
 (1, 2, 5),
 (1, 3, 4),
 (1, 3, 5),
 (1, 4, 5),
 (2, 3, 4),
 (2, 3, 5),
 (2, 4, 5),
 (3, 4, 5)]
"""

permutations

우리가 수학시간에 배웠던 permutation(순열)이 iteration형태로 나온다.
아래는 iteration형태로 나오는 것을 리스트에 담아준 것.

예를 들어 원소가 5개인 permutations(list_a, 3)은 5P3의 조합, combinations(list_a, 2)는 5P2의 조합

순열은 중복을 허용한다.

from itertools import permutations

items = [1, 2, 3, 4, 5]

list(permutations(items, 3))

"""
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 2), (1, 3, 4), (1, 3, 5), (1, 4, 2), (1, 4, 3), (1, 4, 5), (1, 5, 2), (1, 5, 3), (1, 5, 4),
 (2, 1, 3), (2, 1, 4), (2, 1, 5), (2, 3, 1), (2, 3, 4), (2, 3, 5), (2, 4, 1), (2, 4, 3), (2, 4, 5), (2, 5, 1), (2, 5, 3), (2, 5, 4),
 (3, 1, 2), (3, 1, 4), (3, 1, 5), (3, 2, 1), (3, 2, 4), (3, 2, 5), (3, 4, 1), (3, 4, 2), (3, 4, 5), (3, 5, 1), (3, 5, 2), (3, 5, 4),
 (4, 1, 2), (4, 1, 3), (4, 1, 5), (4, 2, 1), (4, 2, 3), (4, 2, 5), (4, 3, 1), (4, 3, 2), (4, 3, 5), (4, 5, 1), (4, 5, 2), (4, 5, 3),
 (5, 1, 2), (5, 1, 3), (5, 1, 4), (5, 2, 1), (5, 2, 3), (5, 2, 4), (5, 3, 1), (5, 3, 2), (5, 3, 4), (5, 4, 1), (5, 4, 2), (5, 4, 3)]
"""

product

product는 집합끼리의 cartesian product를 리턴한다.
permutations와는 달리 두 개의 리스트 (집합)이 필요하다.

from itertools import product

items = [[1, 2, 3, 4, 5], ['a', 'b', 'c', 'd', 'e']]

list(product(*items))

""" 
 result:
[(1, 'a'),
 (1, 'b'),
 (1, 'c,'),
 (2, 'a'),
 (2, 'b'),
 (2, 'c,'),
 (3, 'a'),
 (3, 'b'),
 (3, 'c,'),
 (4, 'a'),
 (4, 'b'),
 (4, 'c,'),
 (5, 'a'),
 (5, 'b'),
 (5, 'c,')]
"""

from itertools import product

items = [[1, 2, 3, 4, 5], ['a', 'b', 'c,'], ['!', '@', '#', '$']]


list(product(*items))

[(1, 'a', '!'),
 (1, 'a', '@'),
 (1, 'a', '#'),
 (1, 'a', '$'),
 (1, 'b', '!'),
 (1, 'b', '@'),
 (1, 'b', '#'),
 (1, 'b', '$'),
 (1, 'c,', '!'),
 (1, 'c,', '@'),
 (1, 'c,', '#'),
 (1, 'c,', '$'),
 
 (2, 'a', '!'),
 (2, 'a', '@'),
 (2, 'a', '#'),
 (2, 'a', '$'),
 (2, 'b', '!'),
 (2, 'b', '@'),
 (2, 'b', '#'),
 (2, 'b', '$'),
 (2, 'c,', '!'),
 
 (2, 'c,', '@'),
 (2, 'c,', '#'),
 (2, 'c,', '$'),
 (3, 'a', '!'),
 (3, 'a', '@'),
 (3, 'a', '#'),
 (3, 'a', '$'),
 (3, 'b', '!'),
 (3, 'b', '@'),
 (3, 'b', '#'),
 (3, 'b', '$'),
 (3, 'c,', '!'),
 (3, 'c,', '@'),
 (3, 'c,', '#'),
 (3, 'c,', '$'),
 
 (4, 'a', '!'),
 (4, 'a', '@'),
 (4, 'a', '#'),
 (4, 'a', '$'),
 (4, 'b', '!'),
 (4, 'b', '@'),
 (4, 'b', '#'),
 (4, 'b', '$'),
 (4, 'c,', '!'),
 (4, 'c,', '@'),
 (4, 'c,', '#'),
 (4, 'c,', '$'),
 
 (5, 'a', '!'),
 (5, 'a', '@'),
 (5, 'a', '#'),
 (5, 'a', '$'),
 (5, 'b', '!'),
 (5, 'b', '@'),
 (5, 'b', '#'),
 (5, 'b', '$'),
 (5, 'c,', '!'),
 (5, 'c,', '@'),
 (5, 'c,', '#'),
 (5, 'c,', '$')]

itertools 라이브러리의 combination 모듈을 활용한 풀이

def solution(number):

 	from itertools import combinations

	count = 0
 	for c in combinations(numbers, 3):
    	if sum(c) == 0:
      	count += 1
        
	return count

더 pythonic한 풀이

def solution(number):
	from itertools import combinataions
    return len([1 for c in combinations(number, 3) if sum(c)==0])

def solution(number):
    from itertools import combinations
    return sum([1 for c in combinations(number, 3) if sum(c)==0])