[해시] Level 2 위장

문제 설명

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

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

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

 

 

제한사항

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

 

입출력 예시와 설명

---

풀이)

우선 이 문제는 해시문제니까 해시 자료구조를 사용해서 해결하였다!

단순히 이 문제를 위해서 해시 자료구조를 정리하고... 파이썬의 딕셔너리를 정리했다...

이 글을 작성하고 C++의 map 자료구조도 정리할 예정...

정리한 건 내 블로그의 염공부였나? 그 카테고리 참고하시길..^^*

---

아무튼! 알고리즘 설명하기!

알고리즘은 그렇게 어렵진 않았다. 그치만 생각하는데는 오래걸림 'ㅅ'

 

우선 의상 종류별로는 1개씩만 선택 가능하기 때문에 해시 테이블에 의상의 종류별로 개수를 구해서 저장했다

예를 들어 clothes가 아래와 같다고 하자

[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]

그러면 해시 테이블에는 아래처럼 저장된다

[["headgear" : 2, "eyewear" : 1]]

 

 

그 후 의상의 종류별로 골라 입을 수 있는 조합의 개수를 구하면 된다

이는 각 종류별 의상 중 선택을 안할 수도 있으니까 '(종류별 의상 개수)+1'을 모두 곱한다

그리고 마지막으로 1을 빼줘야 한다!

왜냐? 모두 선택하지 않은 경우는 없다고 했으므로, 해당 경우는 뺴줘야 한다

 

흠 이해가 어려운 것 같아서 다른 예시를 들어보도록 하겠다

만약, 상의가 스웨터, 반팔, 와이셔츠 이렇게 3 종류가 있다면 가능한 경우의 수는 스웨터, 반팔, 와이셔츠, 아무것도 선택 안 함 이렇게 4가지가 있다 -> 종류별 의상 개수에 1을 더하는 이유

 

만약, 상의 3개, 하의 2개, 장신구 2개가 있었다고 가정하면, 총 가능한 경우의 수는 (3+1) * (2+1) * (2+1) = 36가지 이다. 그런데, 이 경우에는 (상의 선택 안 함, 하의 선택 안 함, 장신구 선택 안 함)이 포함되어 있으므로 그 경우를 빼주는 것이다 -> 마지막에 1을 뺴주는 이유

---

파이썬 코드)

def solution(clothes):
    answer = 1
    dic = {} #dictionary 사용
    
    for i in range(len(clothes)):
        kind = clothes[i][1]
        if kind in dic:
            dic[kind] += 1
        else:
            dic[kind] = 1
            
    for k in dic.keys():
        print(k)
        answer *= (dic[k]+1)
    answer -= 1
    return answer

딕셔너리 자료형을 이용해서 구현하였다

딕셔너리 자료형에 의상의 종류를 key로 하여 의상 종류별 개수를 딕셔너리에 저장한다

그 후 알고리즘대로 1씩 더한 값들을 곱하고 마지막으로 1을 빼서 반환한다

 

C++ 코드)

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map<string, int> m;
    for(int i=0;i<clothes.size();i++)
    {
        string str = clothes[i][1];
        if(m.find(str)!=m.end()) //map에 존재
        {
            m[str]++;
        }
        else //map에 없음
        {
            m.insert({str,1});
        }
    }
    
    //map<string, int>::iterator it; 을 auto 자료형으로 대체!
    for(auto it=m.begin();it!=m.end();it++)
    {
        answer *= (it->second+1);
    }
    answer--;
    return answer;
}

여기서 새로 알게된 건 auto 자료형이랑 iterator!

이것도 얼레벌레 쓰고 있긴한데 조만간 각잡고 정리할 예정이다ㅠ

 

 

---

아 밤샜네,,

원래 7시에 일어나려고 했는데 지금 6시반이야ㅋㅋㅋㅋ

몰라 잘래,,, 빠잉,,,