[Programmers]#Level2_의상, 해시, unordered_map

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. unordered_map

 

[Basic C++] #72_unordered_map

 

unordered_map 컨테이너는 C++ 표준 라이브러리에서 제공하는 연관 컨테이너입니다. unordered_map 컨테이너는 키와 값을 쌍으로 해시 자료구조에 저장하며, 중복을 허용하지 않고 내부적으로 정렬 작업을 수행하지 않습니다.

 

2. 해시 자료구조

 

[Basic C++] #40_해시함수, 비순차 연관 컨테이너, 해시 테이블

 

해시 자료구조는 해시 함수와 해시 테이블로 키와 값을 쌍으로 저장하는 비 선형 연결 자료구조입니다. 해시 자료구조는 입력받은 키를 해시 함수를 통해 '해시 함수'로 변환하고, 이에 대응하는 값을 저장하는 해시 테이블의 인덱스로 활용합니다. 해시 자료구조의 접근 성능은 선형 시간 복잡도로 빠른 접근 성능을 제공하지만, 해시 함수에 대한 강한 의존성과 해시 충돌의 단점이 있습니다.

 

3. 의상 종류 - 갯수를 um에 저장하고, 경우의 수를 세자!

 

1. 먼저, 주어진 의상 정보를 통해 um 컨테이너에 { 의상 종류, 개수 }를 쌍으로 저장합니다.
2. 그리고, um을 순회하며 각 의상 종류 별 개수+1을 거듭해서 곱해주며, 결과 값을 찾습니다.
3. 이때, 최종 결과 값에서 각 의상 종류를 모두 입지 않은 경우를 빼주어야 합니다!

 

---

 

#3. 코드

 

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    unordered_map<string, int> um;
    
    for(int i=0; i<(int)clothes.size(); ++i)
        um[clothes[i][1]]++;
    
    for(auto it = begin(um); it != end(um); ++it)
        answer *= (it->second+1);
    
    return answer-1;
}

 

---