프로그래머스 - 위장

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

 

문제 내용

주어진 스파이의 의상을 보고, 서로 다른 옷의 조합 수를 리턴하자.  

제한 사항

• 배열의 각 요소는 [의상 이름, 의상 종류]로 이루어져 있다.
  • ex) [“yellow_hat”, “headgear”]
• 1 <= 의상의 수 <= 30
• 같은 이름의 의상은 없다.
• 최소 한 개의 의상을 입어야 한다.

   

해시 - O(N)

 

이 문제는 경우의 수를 세는 문제이다.
입력으로 주어지는 의상의 종류와 개수를 센 후,
입을 수 있는 모든 조합의 수를 출력해야 한다.

조합의 수를 어떻게 세어야 할까?
다음과 같은 의상이 있다고 가정하자.

 

종류	이름
상의	흰티, 검은티
하의	청바지
신발	운동화

 

상의는 2종류, 하의는 1종류, 신발은 1종류가 있다.
위의 상황에서의 조합이 어떻게 되는지 살펴보자.

현실에서는 말도 안돼는 일이긴 하지만,
상의만 입을 수도 있고,
하의만 입을 수도 있고,
신발만 신을 수도 있다.
그래도 기분이 뭔가 이상하다면, X는 기본 복장이라고 생각하자.

상의를 고를 수 있는 경우의 수는 몇 가지일까?
흰 티, 검은 티, 혹은 X로 총 3가지이다.

하의를 고를 수 있는 경우의 수는 몇 가지일까?
청바지 혹은 X로 총 2가지이다.

신발을 고를 수 있는 경우의 수는 몇 가지일까?
운동화 혹은 X 로 총 2가지이다.

즉, 모든 가능한 경우의 수는
3가지 x 2가지 x 2가지 = 12가지
가 된다.

이 경우의 수를 표로 확인해보자.

 

?	상의	하의	신발
1	흰티	X	X
2	흰티	X	운동화
3	흰티	청바지	X
4	흰티	청바지	운동화
5	검은티	X	X
6	검은티	X	운동화
7	검은티	청바지	X
8	검은티	청바지	운동화
9	X	X	X
10	X	X	운동화
11	X	청바지	X
12	X	청바지	운동화

 

이 표를 보고 “12개가 답이다!” 라고 하기엔 아직 이르다.
문제의 조건 중 이러한 조건이 있다.

• 스파이는 하루에 최소 한 개의 의상은 입습니다

따라서, 위의 경우의 수 중 아무 것도 입지 않는
(X, X, X)의 경우의 수는 제외해야 한다.
테이블 상에서는 9번 항목을 제외해야 한다.

따라서 (3 x 2 x 2) - 1 = 11가지가 답이 된다.

그러면 이를 일반화하여 식을 세워보자.

의상 1의 개수 c1,
의상 2의 개수 c2,

…

의상 n의 개수 cn이라고 하자.

그러면 가능한 의상의 개수는 다음과 같다.

 

(c1 + 1) x (c2 + 1) x ... (cn + 1) -               1
 의상 1      의상 2         의상 n    모든 의상을 입지 않은 경우의 수

 

이제 어떤 코드를 작성해야 할 지에 대한 계획이 세워졌다.

1. 각 의상의 종류는 몇 가지가 있는가를 확인한다.
2. 각 의상의 종류를 곱하고, 여기에 1을 뺀 수를 리턴한다.

그러면 각 의상 종류의 수를 어떻게 세어야 할까?
여기에서 사용하면 좋은 것이 바로 해시다.

C++은 unordered_map,
Java는 HashMap,
python은 dictionary를 사용하면 된다.

각 배열의 첫 번째 요소(= 인덱스 0)은 의상의 이름이고,
두 번째 요소(= 인덱스 1)은 의상의 종류이다.
따라서 해시맵의 key는 배열의 두 번째 요소(= 인덱스 1)을 사용해야 한다.

그러면 배열의 첫 번째 요소는 어떻게 사용해야 할 까?

문제의 조건 중 이러한 조건이 있다.

• 같은 이름의 의상은 없다

그렇다는 말은, 의상의 이름은 신경 쓸 필요가 없다는 의미이다.
만약 입력 중에 같은 이름의 의상이 나왔고, 이게 답에 영향을 미친다?
조건을 잘못 명시한 문제 출제자의 잘못이니 따지면 된다.
따라서, 우리는 의상의 이름에 신경을 전혀 쓸 필요가 없다.

그러면 이제 코드를 작성해보자.

 

solution.cpp

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> mp;
    
    for (auto pr : clothes) ++mp[pr[1]];
    
    int answer = 1;
    for (auto it : mp)  answer *= it.second + 1;
    
    return answer-1;
}

 

파이썬의 경우,

collections의 Counter

를 이용하면 좀 더 간결한 코드를 작성할 수 있다.
관심이 있으면 찾아보자.