알고리즘 풀이: [프로그래머스] 위장

https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

문제 설명

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

 

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

 

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

 

스파이가 가진 의상들이 담긴 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

 

입출력 예 설명

예제 #1

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

 

1. yellow_hat

2. blue_sunglasses

3. green_turban

4. yellow_hat + blue_sunglasses

5. green_turban + blue_sunglasses

 

예제 #2

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

 

1. crow_mask

2. blue_sunglasses

3. smoky_makeup

---

문제 풀이

옷의 종류가 키이고 해당 종류 옷의 개수를 밸류로 하는 해시 테이블을 구성합니다. 이를 바탕으로 경우의 수를 계산합니다.

 

스파이가 옷을 입는 경우의 수는?

경우의 수 구하기

옷을 입는 경우의 수를 계산할 때, 옷을 입지 않는 경우("no_headgear", "no_eyewear")를 추가합니다. 옷을 입지 않는 경우가 추가되어야 모든 종류의 옷을 갖추지 않는 경우(headgear만 착용하거나 eyewear만 착용하는 경우)가 계산됩니다. 최종적인 경우의 수를 계산할 때에는 모든 종류의 옷을 입지 않는 경우가 포함되어 있으므로 이를 빼야 합니다.

 

따라서, 해시 테이블에 저장된 값들에 모두 +1을 하고 곱합니다. 그리고 마지막에 -1을 하면 옷을 입는 경우의 수를 구할 수 있습니다.

 

소스 코드

메인 솔루션 함수

def solution(clothes):
    hash_table = dict()
    for _, kind in clothes:
        if kind not in hash_table:
            hash_table[kind] = 0
        hash_table[kind] += 1

    number_of_cases = 1
    for value in hash_table.values():
        number_of_cases *= (value + 1)

    number_of_cases -= 1
    return number_of_cases


if __name__ == '__main__':
    assert solution([["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]) == 5
    assert solution([["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]) == 3

 

프로그래머스 결과

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%202/%EC%9C%84%EC%9E%A5.py

dhsong95/-PRACTICE-Programmers-Algorithm