[프로그래머스] 위장 (해시 Lv. 2)

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

코딩테스트 연습 - 위장

1. 풀이 원리 

    1) map으로 옷에대한 count를 구한, 이때 옷을 입지 않는 경우를 계산하여 + 1 한다.

    2) map을 순회 하면서 count를 모두 곱한다. 

    3) 옷을 모두 입지 않는 경우를 제외하기 위해서 -1 한다.

2. 알면 좋은  수학 지식 

    - 인수분해

3. 알야할 코딩 지식

    1) map 종류 : map, unordered_map

        (1) map

            - 구현 방식 : Red-black tree
              https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

        (2) unordered_map 

            - 구현 방식 : hash 방식 

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

Hash table - Wikipedia

 

        (3) 성능 비교

http://veblush.github.io/ko/posts/map-vs-unorderedmap-for-string-key/

 

    2) map 사용법

#include <iostream>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string ,int> u_map;

    // insert
    u_map.insert(std::make_pair("kim", 2));
    u_map["jim"] = 4;


    // find 
    std::cout << u_map.find("kim")->second << std::endl;
    std::cout << u_map["jim"] << std::endl;


    // not found
    if (u_map.find("kin") == u_map.end()) {
        std::cout << "값이 없음" << std::endl;
    }

    // loop
    for (const auto &item : u_map) {
        std::cout << item.first << ":" << item.second << std::endl;
    }

    return 0;
}