[프로그래머스 Lv.2 / C++] Day62. 의상

2024. 08. 04 - 코딩테스트 스터디 Day62

 
 

01. 문제 설명

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

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

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

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

 
 

02. 제한사항

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

 
 

03. 입출력 예

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

04. 풀이 및 답

문제를 풀기 전 모든 조합의 경우의 수 규칙에 대해 생각해 보았다.
 

종류	개수
상의	3
하의	2

만약, 위와 같이 상의 종류의 옷 3개(1, 2, 3), 하의 종류의 옷 2개(a, b)를 소유하고 있다면

1. 1
2. 2
3. 3
4. a
5. b
6. 1a
7. 1b
8. 2a
9. 2b
10. 3a
11. 3b

 

위처럼 11개의 조합을 만들 수 있다.

(3 + 1) * (2 + 1) - 1 = 11
(각 종류에 포함된 옷 개수 + 1)끼리 곱하여 모든 조합의 경우의 수를 구한 뒤,
아무것도 입지 않는 경우의 수(1)를 빼줘야 하는 것이다.

 
 

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

using namespace std;

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

코니가 입을 수 있는 서로 다른 옷의 조합의 수를 담을 변수 answer를 1로 초기화해 준다.
string 타입의 key값, int 타입의 value값을 갖는 unordered_map map을 선언한다.
 
clothes의 두 번째 요소(index가 1), 즉 옷의 종류를 map의 key로 두고, 그 옷의 종류 개수만큼 value를 1씩 증가시킨다.

예를 들어, c[1]은 "headgear", "eyewear" 등과 같은 옷의 종류이고,
이 c[1]들을 map이 key로 갖도록 만들어 그 개수가 value가 되게 했다.

 
그 뒤, map의 각 요소의 value값에 1을 더한 값을 answer에 곱해준다.
마지막으로 answer에서 1을 뺀 값을 리턴한다.
 
 

정답!
 
 

05. unordered_map 개념 정리

나중에 헷갈릴까봐 정리
 

1. 해시 맵의 key와 value

map[A] = B;

위와 같은 구조라면, A는 map의 key, B는 map의 value
 

2. 해시 맵의 key와 value 접근 방법

☝🏻 key에 접근하기

c.first
c->first	// c가 포인터일때

 
✌🏻 value에 접근하기

c.second
c->second	// c가 포인터일때

 
위 문제에서는 c는 unordered_map<string, int>의 요소이므로 포인터가 아닌 객체로 접근했다.

---

해시 맵 처음 볼 땐 너무 어려웠는데 이제 나름 감을 잡은 것 같아서 뿌듯하다