주제 - “알고리즘 (해시) - 3”
부제 - 프로그래머스 코딩테스트 연습 - 파이썬
출처 - 프로그래머스 - 코딩테스트 연습 - 해시 - 위장
- 문제의 풀이는 다른 사람의 풀이 중 공부하고 싶은 것을 스크랩한 것입니다.
문제 3. 위장
[문제 설명]
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
| 종류 | 이름 |
|---|---|
| 얼굴 | 동그란 안경, 검정 선글라스 |
| 상의 | 파란색 티셔츠 |
| 하의 | 청바지 |
| 겉옷 | 긴 코트 |
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
[제한사항]
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ‘_’ 로만 이루어져 있습니다.
- 스파이는 하루에 최소 한 개의 의상은 입습니다.
[입출력 예]
| clothes | return |
|---|---|
| [[“yellow_hat”, “headgear”], [“blue_sunglasses”, “eyewear”], [“green_turban”, “headgear”]] | 5 |
| [[“crow_mask”, “face”], [“blue_sunglasses”, “face”], [“smoky_makeup”, “face”]] | 3 |
풀이
from collections import Counter
from functools import reduce
def solution(clothes):
cnt = Counter([kind for name, kind in clothes])
answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
return answer
풀이의 포인트
clothes 리스트를 통해 가진 옷을 매칭하는 경우의 수를 확인하는 문제입니다. 이는 옷의 종류별로 최소 0개에서 최대 1개를 선택해 입을 수 있음을 파악하는 것이 우선입니다. 단, 최소 한 개의 의상은 입는다는 조건이 있으므로 모든 경우의 수에서 모든 종류에서 0개를 선택할 경우의 수 하나를 제외해야 합니다.
옷을 선택하는 경우의 수를 고려하기 위해서, 옷의 종류별로 가진 개수를 파악하는 것이 선행되어야 합니다.
1) 옷의 종류별 개수 확인을 위한 Counter 클래스
Counter 클래스는 지난 문제에서도 사용한 적이 있기에 따로 설명을 작성하지 않습니다.
for문( kind for name, kind in clothes )을 이용해 clothes 리스트의 [][1] 인덱스 값만을 추출하고, 그를 Counter를 이용해 카운팅합니다. 이 결과로 옷의 종류별 개수를 파악할 수 있습니다.
>>> clothes = [['yellow_hat', 'headgear'], ['blue_sunglasses', 'eyewear'], ['green_turban', 'headgear']]
>>> for name, kind in clothes:
print ("name = ", name, "/ kind = ", kind)
name = yellow_hat / kind = headgear
name = blue_sunglasses / kind = eyewear
name = green_turban / kind = headgear
>>> [kind for name, kind in clothes]
['headgear', 'eyewear', 'headgear']
>>> Counter([kind for name, kind in clothes])
Counter({'headgear': 2, 'eyewear': 1})
2) functools 모듈의 reduce: iterable의 element들을 왼쪽에서부터 함수에 적용시켜, 단일 값으로 뽑아내는 클래스
- reduce에는 인자로 function, iterable 와 함께 선택적으로 initializer가 올 수 있음
initializer가 존재하는 경우, 이는 iterable의 첫번째 값처럼 function에 적용됨
- lambda : 이름없는 함수를 생성하기 위한 표현법으로, reduce의 인자로 자주 사용됨
ex)
>>> reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) 15 # ( ( ( 1 +2 ) +3 ) +4 ) +5 >>> reduce(lambda x, y: x+y, [1, 2, 3, 4, 5], 1) 16 # ( ( ( ( 1 +1 ) +2 ) +3 ) +4 ) +5
reduce를 사용하여, 종류별 옷의 개수를 가지고 경우의 수를 계산합니다. 경우의 수 계산을 위해, 옷의 종류별 개수에 1을 더해 모두 곱합니다. 1을 더하는 이유는 아무것도 선택하지 않는 경우를 추가하는 것입니다.
가령, headgear가 [a, b, c] 인 경우에는 아무것도 선택하지 않는 경우, a를 선택하는 경우, b를 선택하는 경우, c를 선택하는 경우의 4가지 경우가 존재하는 것입니다.
그리고 각 종류별 경우의 수는 동시에 수행되므로 곱하기를 이용해 연산합니다.
마지막으로, 모든 종류의 옷에서 0개를 선택하는 경우 하나를 제외합니다. 이 과정을 모두 수행하면 서로 다른 옷의 조합의 수가 계산되는 것입니다.
>>> cnt = Counter([kind for name, kind in clothes])
>>> cnt
Counter({'headgear': 2, 'eyewear': 1})
>>> reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
5 # ( ( 1 * (2+1) ) * (1+1) ) - 1