[파이썬/알고리즘] 프로그래머스 - 의상

[문제]

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

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

종류 이름
얼굴 동그란 안경, 검정 선글라스
상의 파란색 티셔츠
하의 청바지
겉옷 긴 코트
코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

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

 

[풀이]

def solution(clothes):
    clothes_dict = {}
    
    for item, category in clothes:
        if category in clothes_dict:
            clothes_dict[category].append(item)
        else:
            clothes_dict[category] = [item]
    
    answer = 1
    for category in clothes_dict:
        answer *= (len(clothes_dict[category]) + 1)
    
    return answer - 1

 

프로그래머스에서는 해시 문제로 분류되어 있지만 해시가 아닌 다른 방법으로 풀었다.

푸는 방법은 같은 종류끼리 묶어주고, 각 카테고리에서 아이템을 선택하는 모든 경우의 수를 계산하면 끝이다.

 

clothes_dict = {}

새로운 딕셔너리를 만들어준다. 이 딕셔너리에는 카테고리를 Key로 아이템을 Value로 갖게 된다.

 

for item, category in clothes:

item, category에 대해서 반복하게 된다.

문제에서 보면 [아이템, 카테고리], [아이템, 카테고리] 이런 식으로 되어 있다.

따라서 itme, category 이런 식으로 반복문을 짜주었다.

 

if category in clothes_dict:

      clothes_dict[category].append(item)

else:
     clothes_dict[category] = [item]
처음 if문에는 카테고리가 있으면 그 카테고리에 item을 더해준다.

즉 문제에서 [["yellow_hat", "headgear"], ["green_turban", "headgear"]] 이렇게 되어 있다고 가정하면 맨 처음에는 카테고리인 headgear이 없기 때문에 else문으로 가서 yellow_hat은 아이템으로 headgear은 카테고리로 들어가게 된다.

두 번째 green_turban부터는 이미 headgear이라는 카테고리가 들어가 있기 때문에 if문을 만족하므로 green_turban만 아이템으로 append 하게 된다.

 

answer = 1

for category in clothes_dict:
   answer *= (len(clothes_dict[category]) + 1

반복문에서 곱셈을 하기 때문에 0 으로 선언하면 안되기 때문에 1로 선언해준다.

반복문을 돌면서 각 경우의 수를 계산하게 된다.

 

"headgear": ["yellow_hat", "green_turban"],

"eyewear": ["blue_sunglasses"]

 

이렇게 있다고 했을 때, 처음에 headgear에 길이에다가 + 1을 해줘서 answer에 곱해준다.

그럼 answer은 초기값이 1 이고 len(clothes_dict[category]) + 1은 3이므로 1 * 3해서 answer은 3이 된다.

 

다음으로는 eyewear에 길이에다가 +1을 해줘서 answer에 곱해준다.

그럼 answer은 위에서 3이었고, len(clothes_dict[category]) + 1은 2이므로 3*2 해서 answer은 6이 된다.

 

return answer - 1

최종적으로는 answer에서 - 1을 해주면 된다.

 

 

왜 +1을 해주고 마지막에 -1을 해주는지 명확하게 얘기하자면 문제에서는 꼭 모든 카테고리에 대해서 무조건 하나씩 입어야 한다는 조건이 없고, 한 카테고리에서만 입어도 된다고 했다. 또 한 아예 안 입는 조건도 없다.

따라서 아래 예시를 가지고 경우의 수를 계산한다면 이렇다.

 

"headgear": ["yellow_hat", "green_turban"],

"eyewear": ["blue_sunglasses"]

 

 

• headgear에서 아무 것도 선택하지 않음, eyewear에서 아무 것도 선택하지 않음
• headgear에서 아무 것도 선택하지 않음, eyewear에서 blue_sunglasses 선택
• headgear에서 yellow_hat 선택, eyewear에서 아무 것도 선택하지 않음
• headgear에서 yellow_hat 선택, eyewear에서 blue_sunglasses 선택
• headgear에서 green_turban 선택, eyewear에서 아무 것도 선택하지 않음
• headgear에서 green_turban 선택, eyewear에서 blue_sunglasses 선택

 

+ 1을 해줘야, 카테고리에서 아무것도 선택하지 않는 선택지를 추가할 수 있다.

 

만약 +1을 안 해준다면,  이 경우의 수만 선택하는 것과 같다. 문제에서 각 카테고리마다 하나씩 입어야 한다면 이게 정답이겠지만 한 카테고리에 대해선만 입으면 나머지 카테고리는 입어도 되고, 안 입어도 되기 때문에 안 입는 경우의 수를 추가해줘야 한다.

• headgear에서 yellow_hat 선택, eyewear에서 blue_sunglasses 선택
• headgear에서 green_turban 선택, eyewear에서 blue_sunglasses 선택

하지만 +1을 하면 모든 카테고리에서 아무것도 선택하지 않는 경우의 수가 있고 이것은 문제에서 원하는 경우가 아니기 때문에 이것은 빼줘야 해서 마지막에 answer에서 -1을 해주는 것이다.