[프로그래머스/C++] Level2 - 의상 #const auto #unordered_map #map #pair

 

의상 [ 링크 ]

Today I Learned: ]

1. unordered_map
2. map
3. const auto
4. unordered_map은 데이터 없으면 기본값 부어. int는 default 0
    그래서 만약 값을 한번도 넣지 않았다면? seq.find() == seq.end() 가 true인 경우 값을 한 번도 안 넣은 거로 간주

 

풀이 방법

서로 다른 의상 종류대로 입는 경우의 수 - 1(안입는 경우의 수)

 

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <numeric>

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> dict(clothes.size());
    for (const auto& cloth : clothes) {
        dict[cloth[1]]++;
    }
    return accumulate(dict.begin(), dict.end(), 1, [](int acc, const auto& e) {
        return acc * (e.second + 1)
    }) - 1;
}

 

새로 알게된 개념

---

unordered_map 과 map

개념은 같다.

 

std::unordered_map의 내부 구조는 해시 테이블.

key 접근, 삭제, 추가 O(1)

순서 보장x

 

 

std::map

key 삽입, 삭제, 검색 속도 O(logN) 보장(데이터 100만 개 -> 거의 20번 정도 비교로 찾음).

레드블랙트리.

key 자동 오름차순 정렬

 

[ ] 대괄호 접근을 할 때 값이 없는 경우 디폴트 값을 넣어준다. 데이터가 없는 경우는 find()를 통해서 dict.end()와 같은 iterator라면 값을 한 번도 넣지 않았음을 알 수 있다. 

 

 

순회 방법

unordered_map<string, int> dict;
dict["apple"] = 100;
dict["banana"] = 200;
dict.erase("apple");

/// find를 쓰면 iterator를 받는거심
/// 값 접근은 *it 이렇게하면 pair가 나오게됨 
/// (*it).second
/// 귀찮다? 
/// it->second
auto it = dict.find("bbbb");
if (it!=dict.end()) {
	dict.erase(it); // 값 접근은 *it
}

for (const auto& [key, value] : dict) {
	cout << "Key" << key << ", value" << value ;
}

 

접근할 때 이렇게 pair객체로 준다. 이는 algorithm의 순회하는 고차 람다 함수들 사용할 때도 pair로 접근 할 수 있다. 

 

find 는 iterator로 반환한다. 조심하자. it은 piar의 주소를 참조하는 객체다.

unordered_map, map의 요소들은 key, value "std::pair"로 되어있다.

 

C++17부터 도입된 구조적 바인딩 쓰면 pair에서 first, second 모호하게 안쓰고 의미부여할 수 있어 편하다.

 

pair<int, string> tuple = {10, "hi"};

auto [id, text] = tuple;

 

이 로직은 포문 루프에 당연 적용됨.

 

/// auto ㅇㅅㅇ
auto operator = [](int acc, const auto& e) {
	return acc * (e.second+1);
}

/// 타입 명시
auto _operator = [](int acc, const std::pair<const string, int>& e) {
    return acc * (e.second+1);
}

 

const auto 좋네. 한 번 공부해보자.

 

const 와 &?

& (Reference : 참조)

원본 참조

 

&를 안쓴다 == 복사본 ( 거의 디폴트 )

const 상수 ( 읽기 전용 )

auto : 컴파일러가 타입추론 알아서 해준다.

 

그래서 이 조합들을 for 문에서 쓰면,

 

1. const auto& 

    - 빠르고 안전

    - 원본 참조하기 때문에 빠름 수정하려는 로직이 보이면 컴파일 단에서 에러 발생시킴

    - 원본을 오직 읽기만 하자

 

2. auto& 

    - 수정 가능한 원본

 

3. auto 

    - 원본들을 복사

    - 포문 돌 때마다 element를 매번 복사해서 사용함

 

4. const auto 안씀