[파이썬을 파이썬답게] Itertools / Collections 모듈

📙 곱집합(Cartesian product) 구하기 - product

🔔 강의 Tip

파이썬의 itertools.product를 이용하면 for문을 사용하지 않고도 곱집합을 구할 수 있다.

   import itertools
   
   iterable1 = 'AB'
   iterable2 = 'xy'
   iterable3 = '123'
   print(list(itertools.product(iterable1, iterable2, iterable3)))
   
   #결과
   [('A', 'x', '1'), ('A', 'x', '2'), ('A', 'x', '3'), 
    ('A', 'y', '1'), ('A', 'y', '2'), ('A', 'y', '3'), 
    ('B', 'x', '1'), ('B', 'x', '2'), ('B', 'x', '3'), 
    ('B', 'y', '1'), ('B', 'y', '2'), ('B', 'y', '3')]

곱집합(Cartesian product)

$A \times B = \left \{ \left ( x, y \right )| x \in A , y \in B \right \}$

각 집합의 원소를 각 성분으로 하는 튜플들의 집합으로 데카르트 곱이라고도 함

📙 2차원 리스트를 1차원 리스트로 만들기

문제 설명
문자열을 담은 이차원 리스트, mylist가 solution 함수의 파라미터로 주어집니다. solution 함수가 mylist를 일차원 리스트로 만들어 리턴하도록 코드를 작성해주세요.

제한 조건

• arr의 길이는 1 이상 100 이하인 자연수입니다.
• arr 원소의 길이는 5를 넘지 않습니다.

---

입출력 예

mylist	output
[[1], [2]]	[1, 2]
[['A', 'B'], ['X', 'Y'], ['1']]	['A', 'B', 'X' ,'Y', '1']

🔔 내 풀이

answer = []
for l in mylist:
    answer += l    
  
return answer

🔔 강의 Tip

파이썬에서는 for문을 사용하지 않고 리스트를 이어붙일 수 있는 다양한 방법이 있음

my_list = [[1, 2], [3, 4], [5, 6]]

# 방법 1 - sum(iterable, start=0)
answer = sum(my_list, [])

# 방법 2 - itertools.chain.from_iterable(iterable)
import itertools
list(itertools.chain.from_iterable(my_list))

# 방법 3 - itertools와 unpacking
# itertools.chain(*iterables)
import itertools
list(itertools.chain(*my_list))

# 방법 4 - list comprehension 이용
[element for array in my_list for element in array]

# 방법 5-1 - reduce(function, iterable, initializer=None)
from functools import reduce
list(reduce(lambda x, y: x+y, my_list))

# 방법 5-2 - reduce(function, iterable, initializer=None)
from functools import reduce
import operator
list(reduce(operator.add, my_list))

# 방법 6 - numpy 라이브러리의 flatten 이용
# 제한적으로 사용 가능한 방법
# 아래의 방법은 각 원소의 길이가 동일한 경우에만 사용 가능
import numpy as np
np.array(my_list).flatten().tolist()

📙 순열과 조합

문제 설명
숫자를 담은 일차원 리스트, mylist에 대해 mylist의 원소로 이루어진 모든 순열을 사전순으로 리턴하는 함수 solution을 완성해주세요.

제한 조건
mylist 의 길이는 1 이상 100 이하인 자연수입니다.

---

입출력 예

mylist	output
[2, 1]	[[1, 2], [2, 1]]
[1, 2, 3]	[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

🔔 내 풀이

def recursion(mylist, answer, tmp, n):
    if n == 0:
        answer.append([i for i in tmp])
      
    for i in range(n):        
        tmp.append(mylist.pop(i))
        recursion(mylist, answer, tmp, n-1)
        mylist.insert(i, tmp.pop())
  
def solution(mylist):    
    answer = []
    mylist.sort()    
    recursion(mylist, answer, [], len(mylist))    
    return answer

🔔 강의 Tip

파이썬의 itertools.permutations를 이용하여 순열을 구할 수 있다.

import itertools

pool = ['A', 'B', 'C']
print(list(map(''.join, itertools.permutations(pool)))) # 3개의 원소로 수열 만들기
print(list(map(''.join, itertools.permutations(pool, 2)))) # 2개의 원소로 수열 만들기

조합의 경우 itertools.combinations를 이용하여 구할 수 있다.

순열(Permutation)

$_{n}\textrm{P}_{r} = \frac{n!}{(n-r)!}$

n개의 원소 중 r개의 원소를 꺼내는 경우의 수
순서가 유효하기 때문에 원소의 중복을 허용함 [1, 2, 3] ≠ [3, 2, 1]
예 : [1, 2, 3] 중 2개를 선택하여 만들 수 있는 모든 숫자를 구하라 👉 $_{3}\textrm{P}_{2}$

def permutation(arr, tmp, n, r):
    """
    :param arr (list) : 원본 리스트
    :param tmp (list) : 결과 리스트(경우의 수 1개)
    :param n   (int)  : 전체 개수
    :param r   (int)  : 뽑을 개수
    """
     if r == 0:
        print(tmp) 
     
     for i in range(n):        
        tmp.append(arr.pop(i))
        permutation(arr, tmp, n-1, r-1)
        arr.insert(i, tmp.pop())  

조합(Combination)

$_{n}\textrm{C}_{r} = \frac{_{n}\textrm{P}_{r}}{r!} = \frac{n!}{r!(n-r)!}$

n개의 원소 중 r개의 원소를 꺼내는 경우의 수
순서가 유효하지 않기 때문에 원소의 중복을 허용하지 않음 [1, 2, 3] = [3, 2, 1]
예 : [1, 2, 3] 중 2개를 곱해서 만들 수 있는 모든 숫자를 구하라 👉 $_{3}\textrm{C}_{2}$

def combination(arr, tmp, idx, n, r):
    """
    :param arr (list) : 원본 리스트
    :param tmp (list) : 결과 리스트(경우의 수 1개)
    :param idx (int)  : 뽑을 차례(반복문 시작 인덱스)
    :param n   (int)  : 전체 개수
    :param r   (int)  : 뽑을 개수
    """
     if r == 0:
        print(tmp) 
     
     for i in range(idx, n):        
        tmp.append(arr[i])
        combination(arr, tmp, i+1, n, r-1)
        tmp.pop()

📙 가장 많이 등장하는 알파벳 찾기

문제 설명
이 문제에는 표준 입력으로 문자열, mystr이 주어집니다. mystr에서 가장 많이 등장하는 알파벳만을 사전 순으로 출력하는 코드를 작성해주세요.

제한 조건

• mystr의 원소는 알파벳 소문자로만 주어집니다.
• mystr의 길이는 1 이상 100 이하입니다.

---

입출력 예

input	output
'aab'	'a'
'dfdefdgf'	'df'
'bbaa'	'ab'

🔔 내 풀이

mystr = 'aab'
mylist = list(mystr)
cntlist = list(set((mylist.count(x), x) for x in mylist))
cntlist.sort()

max_cnt, _ = cntlist[-1]
res = [ch for cnt, ch in cntlist[::-1] if cnt == max_cnt]

print(''.join(sorted(res)))

🔔 강의 Tip

파이썬의 collections.Counter클래스를 이용하여 어떤 원소 x가 주어진 sequence에 몇 번이나 등장하는지 구할 수 있다.

import itertools

mylist = [1, 2, 3, 4, 5, 6, 7, 8, 7, 9, 1, 2, 3, 3, 5, 2, 6, 8, 9, 0, 1, 1, 4, 7, 0]
collections.Counter(mylist)
print(answer[1]) # = 4
print(answer[3])  # = 3
print(answer[100]) # = 0

Programmers - 파이썬을 파이썬답게 https://programmers.co.kr/learn/courses/4008