프로그래머스 Lv2 의상 (python)

의상

 

풀이

처음엔 모든 경우의 수를 구하기 위해, 재귀함수를 이용해 모든 옷을 입을 수 있는 방법을 구하도록 하였다.
방법에는 문제가 없는 것으로 보이나, 시간이 너무 오래 걸리게 되어 실패했다.

# 코니는 매일 다른 옷을 조합. 종류별, 1가지 의상만 착용
# 다른 의상이 겹쳐도, 다른 의상이 겹치지 않거나 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 착용한 것.
# 코니는 하루에 최소 한 개의 의상

# 변수 설정
answer = 0
clothes_kind = []
# 옷을 입는 방법을 추가
# puton(clothes_dict, 착용갯수, 착용 의상 인덱스, 입은 의상 리스트)
def puton(clothes_dict, i, j, put_cloth):
    global answer
    # 입은 의상 갯수가 착용 갯수와 동일하면 answer +1하고 return
    if len(put_cloth) == i:
        answer += 1
        return
    # j가 len(clothes_kind)가 되면 의상 확인은 끝까지 다 했으니, return
    if j == len(clothes_kind):
        return
    # 의상 착용을 재귀함수 이용하기, 각 의상 종류 안에서의 리스트를 돌리는 것임.
    for k in range(len(clothes_dict[clothes_kind[j]])):
        puton(clothes_dict, i, j+1, put_cloth+[clothes_dict[clothes_kind[j]][k]])
    # 해당 종류의 의상을 입는 방법도 있지만, 안입고 넘기는 경우도 있으니, 이를 확인.
    puton(clothes_dict, i, j+1, put_cloth)

# 문제 풀이 solution함수
def solution(clothes):
    global answer
    global clothes_kind
    clothes_dict = {}
    
    for cloth in clothes:
        if clothes_dict.get(cloth[1]):
            clothes_dict[cloth[1]].append(cloth[0])
        else:
            clothes_dict[cloth[1]] = [cloth[0]]
    clothes_kind = list(clothes_dict)
    max_put = len(clothes_dict)
    # 1개씩만 착용 했을 때.
    # possible = len(clothes)
    # 1개 부터 max_put개 까지 착용을 하게 하면
    for i in range(1, max_put+1):
        puton(clothes_dict, i, 0, [])
    
    return answer

그래서 아래 처럼 다른 풀이 방법으로 풀게 되었다.
경우의 수를 그대로 이용해서, 모든 옷의 종류 별로 개수를 구하고, 그 수를 각각 곱해준 뒤 모두 안 입는 경우를 제외하는 것이다.
1. clothes_dict에 모든 옷의 종류 별 옷의 개수를 입력시킴
2. answer = 1로 설정하고, 각 옷의 종류별, (옷의 개수+안 입는 경우)를 answer에 곱해준다.
3. 결과 반환에서 모든 의상을 착용하지 않는 경우를 제외해서, answer -1을 반환한다.

def solution(clothes):
    clothes_dict = {}
    # clothes의 각 종류 별로 분류 및 종류별 갯수 확인
    for cloth in clothes:
        if clothes_dict.get(cloth[1]):
            clothes_dict[cloth[1]] += 1
        else:
            clothes_dict[cloth[1]] = 1
    answer = 1
    
    # 각 의상 종류의 value인 종류별 갯수를 answer에 곱하기
    for value in clothes_dict.values():
        # value + 1인 이유는 모든 옷의 갯수와 안입는 경우의 갯수를 합하기 때문
        answer *= (value + 1)
        
    # 모든 것을 착용 안 하는 경우를 빼주기만 하면 정답
    return answer - 1

휴.. 사람은 머리를 잘 써야하는구나 흑흑 힘들었다.

다른 사람 풀이

내가 2번째로 푼방법과 같다.
Counter 함수를 사용했다.
똑똑한 사람이 너무 많다 흑흑흑

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer