[프로그래머스] 위장

chanyeong kim·2021년 12월 30일

hash 프로그래머스

프로그래머스

목록 보기

42/51

vue image

📩 -->문제설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]	3

💡 solution(사용언어: python)

from itertools import combinations
def solution(clothes):
    answer = []
    kind=list(zip(*clothes))
    for i in range(1, len(set(kind[-1]))+1):
        for k in list(combinations(kind[-1],i)):
            if len(k)==len(set(k)):
                answer.append(k)
    return len(answer)

👉 설명

clothes에는 옷의 종류가 담겨 있고 각각의 종류들의 조합을 구하면 조건을 만족하기 때문에 위와 같이 짰다!
그런데 시간초과로 실패한 케이스들이 존재 했다.
아무래도 모든 조합으르 만들고 set을 해주다 보니 효율성이 좋지 못했다.

💡 Solution 보완

def solution(clothes):
    answer=1
    kind=list(zip(*clothes))
    result={i:0 for i in list(set(kind[1]))}
    for i in kind[1]:
        result[i]+=1
    for i in result.values():
        answer=answer*(i+1)
    return answer-1

고민하던 중 우연히 경우의 수 관련 내용을 보게 되었다
a,b,c로 조합 가능한 모두의 경우의 수는 a x b x c
하지만 안 입는 경우도 존재하기 때문에 각각 +1을 해줌
(a+1)(b+1)(c+1)
마지막으로 a,b,c 전부 안입는 경우는 제외해야 하므로 -1을 해준다
즉 (a+1)(b+1)(c+1) -1 을 구하는 코드를 짜면 된다!

다른 풀이 (1)

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

눈여겨본 코드 중에 하나인데, counter와 reduce를 이용했다.
counter은 옷 종류마다 각각 갯수를 카운트 해준다.
reduce는 누적 집계를 해주는 것으로 reduce(function, iterable, initializer=None) 이렇게 사용한다.
reduce(lambda x, y: x(y+1, cnt.values(),1))
cnt.values=[2,1] 이라면
1*(2+1)
(1*(2+1))(1+1) 이렇게 진행된다!

다른 풀이 (2)

def solution(clothes):
    clothes_type = {}

    for c, t in clothes:
        if t not in clothes_type:
            clothes_type[t] = 2
        else:
            clothes_type[t] += 1

    cnt = 1
    for num in clothes_type.values():
        cnt *= num

    return cnt - 1