프로그래머스 의상

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

프로그래머스

 

이 때 map과 unordered_map의 차이는
key를 기준으로 정렬 O -> map
key를 기준으로 정렬 X -> unordered_map
key값으로 hash value를 찾는데 unordered_map가 훨씬 빠르다고 한다(평균 O(1))
또한, map을 초기화하지 않은 상태에서 현재 key가 존재하지 않지만, map[key]++을 하면 0으로 초기화 된 후 ++연산을 하기 때문에 어떤 개수를 체크할 때 사용하기 좋다고 한다.

 

 

처음 이문제를 접했을 때 2차원 배열을 hash처럼 key, value 값으로 구현하면 되겠다고 생각을 했다.

옷 종류와 이름을 hash_map에 넣기 위해 unordered_map을 사용했다.

unordered_map로 해시를 적용하여 옷의 종류에 따른 갯수를 저장했다.

내가 참고했던 조합을 구하는 방식은 다음과 같다.

 

알고리즘

1. 옷 종류마다 갯수에 1(안 입는 경우의 수)을 더한다.
2. 1을 더한 갯수들을 모두 곱한다.
3. 마지막으로 1(아무것도 안 입는 경우의 수)을 빼준다.

즉, 예를 들어 두 종류가 있다면 (한 종류의 옷의 갯수 + 1)(한 종류의 옷의 갯수 + 1) - 1 이다.

 

코드

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

using namespace std;

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