[4코1파] #28. 위장

gunny·2023년 1월 31일

4코1파 위장 python 코딩테스트 코딩테스트 python 프로그래머스 위장 프로그래머스 위장 PYTHON

코딩테스트

목록 보기

28/530

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (28일차)
[4코1파] 2023.01.13~ (19일차)

Today :

2023.01.31 [28일차]

프로그래머스 LV2.
위장
https://school.programmers.co.kr/learn/courses/30/lessons/42578

문제 요약

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

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

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

제한 사항

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

입출력 예

예제 #1

headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

예제 #2

face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

문제 풀이 방법

리스트에 주어져있는 해당 의상에 따라서 딕셔너리를 만든 후에,
딕셔너리에 있는 value의 길이 만큼 조합을 구하는 문제 였는데

처음 풀 때는 딕셔너리에 넣고 나서, 각 딕셔너리에 있는 키의 개수에 따라서, 조합의 개수를 구했지만 번번히 실패하지요?

여러 테스트 코드에 실패

로직이 잘못된 것은 알았지만, 값에 대한 조합의 값을 어떻게 구해야할지 모르겠다... 분명히 permutations 쓰면 시간복잡도에서 나가리 될 것 같아서.. 문제 해결을 보다가 어떤 천재가 다항식 문제라는 걸 알려줬다

암튼 저 힌트로 딕셔너리에 있는 value에 대하여 계수마다 1을 더해서 곱해주는 형식으로 answer를 구할 수 있었다..

내 코드

from math import prod

def solution(clothes):
    clothes_dict = {}
    
    for clothe in clothes:
        if clothe[1] not in clothes_dict.keys():
            clothes_dict[clothe[1]] = [clothe[0]]
        else:
            clothes_dict[clothe[1]].append(clothe[0])
    
    answer = prod([len(v)+1 for v in clothes_dict.values()])-1
    
    return answer