위장 - 프로그래머스

코딩테스트 연습 - 위장

문제 설명

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

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

종류이름

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

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

제한사항

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

---

요약하면 '최소 하나 이상의 옷을 입는 경우의 수를 구한는데, 한 부분에 2개 이상 걸칠 수 없다.'이다

내 해결 방법은 이렇다.

1. key-value 자료구조를 만든다. 이하 설명에서 맵이라 한다.
2. 맵의 key는 종류, value는 해당 종류의 옷의 가짓수이다. 만약 '옷'이 2종류라면 { '옷': 2 }이다.
3. 해당 종류와 가짓수로 입을 수 있는 경우의 수를 구한다.

3번에서 해당 종류와 가짓수를 입을 수 있는 경우의 수는, (각 종류의 가짓수 + 1)들의 곱 - 1이다.
즉, 옷 2종류, 신발 4종류가 있다면, (2 + 1) * (4 + 1) - 1 = 14가지이다. +1은 해당 종류를 입지 않는 경우이고, -1은 모든 종류를 입지 않는 경우 하나를 제외하는 것이다.

 

위의 해결 방법을 코드로 해결하기 위한 순서는 다음과 같다.

1. key-value 자료구조 객체를 생성한다. 이하 설명에서 map이라 한다.
2. 입력으로 들어온 옷 리스트에 대하여 다음을 실행한다.
   1. 옷의 종류가 map에 없다면, 새 값을 생성한다. key는 종류, value는 0으로 설정한다
   2. 해당 종류를 key로 갖는 value를 1만큼 더한다.
3. map에 있는 모든 value에 대해 실행한다. (answer 변수 생성 후 1로 초기화)
   1. answer에 (value + 1)만큼을 곱한다.
4. answer에서 1을 빼준다.

answer은 곱연산을 위해 1로 초기화 해준다.
만약 제한사항에 '최소 한 개의 의상은 입는다'는 조건이 있더라도 순서는 변하지 않는다.
왜냐하면 4번에서 1을 빼주기 때문에, answer은 0이 된다.

만약 같은 이름을 가진 의상이 존재한다는 문제였다면, map의 value를 key-value 객체로 만든 다음 key로 의상의 이름을 넣는다. 그런다음 2-2의 value 대신 key의 갯수를 넣어준다.

 

위의 순서를 코드로 작성하면 다음과 같다

def solution(clothes):
    # 1. key-value 자료구조 객체를 생성한다. 이하 설명에서 map이라 한다.
    map = {}
    
    # 2. 옷 리스트에 대하여
    for list in clothes:
    	# 2-1. 옷의 종류가 map에 없다면, 새 값을 생성한다
        part = list[1]
        if part not in map:
            map[part] = 0
        
        # 2-2. 해당 종류를 key로 갖는 value를 1만큼 더한다.
        map[part] = map[part] + 1;
        
    # 3. map에 있는 모든 key에 대하여 (answer 변수 생성 후 1로 초기화)
    answer = 1
    for key in map:
    	# 3-1. answer에 (value + 1)만큼을 곱한다.
        answer = answer * (map[key] + 1)
    
    # 4. answer에서 1을 빼준다.
    answer = answer - 1
    
    return answer