[백준] 17219 비밀번호 찾기 C++

https://www.acmicpc.net/problem/17219

---

코드

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    unordered_map<string, string> memo;

    int n, m;
    cin >> n >> m;

    for(int i=0; i<n; i++) {
        string site;
        string password;
        cin >> site >> password;

        memo[site] = password;
    }

    for(int i=0; i<m; i++) {
        string siteToFind;
        cin >> siteToFind;

        cout << memo[siteToFind] << '\n';
    }

    return 0;
}

---

💡 해시 테이블

key-vlaue 쌍을 저장하는 데이터 구조
검색, 삽입, 삭제가 모두 평균 O(1)의 시간 복잡도를 가짐 !!

💡 unordered_map

C++에서 해시테이블은 unordered_map을 통해 사용가능

#include <unordered_map>

// key와 value의 타입 지정
unordered_map <string, string> um;

사용법

empty( )

• 맵이 비어있는지 확인
• 비어있다면 true, 비어있지 않다면 false 반환
• um.empty()

size( )

• 맵의 원소 수 반환
• um.size()

operator[ ]

• 주어진 key에 대한 value 참조
• 만약 해당 key가 없다면 새로운 key-value 쌍 추가
• um[key] = value

find( key )

• 맵에서 key에 해당하는 원소를 찾는 함수
• 존재하지 않을 경우 um.end() 반환
• um.find("apple")

count( key )

• 맵에서 key에 해당하는 원소의 개수를 반환
• unordered_map은 중복 허용하지 않음 -> 존재하면 1, 존재하지 않으면 0
• um.count("apple")

insert( {key, value} )

• 맵에 key-value 쌍 삽입
• 이미 key 존재하면 삽입 x
• um.insert({"apple", 3})

erase( key )

• 맵에서 key에 해당하는 원소 제거
• um.erase('apple')

clear( )

• 맵 초기화, 맵의 모든 원소 제거

---

✏️ 공부한 것들

1. key-value 생성

• um[key] = value;
  - 해당 key가 존재하면 value 업데이트해당
  - key가 존재하지 않는다면 key-value 삽입
• um({key, value});
  - 해당 key가 존재하지 않을 때만 value 삽입
  

2. find()의 사용

find
맵에서 key를 검색하고, 해당 key가 존재하면 해당 원소를 가리키는 iterator를 반환. key가 존재하지 않으면 um.end()를 반환.

auto tmp = um.find("key");
if (tmp != um.end()) { 
	//존재
    cout << "key: " << tmp->first << '\n';
    cout << "value: " << tmp->second;
} else {
	// 존재하지 않음
    cout << "not found";
}

tmp -> first == key
tmp -> second == value

3. key에 대한 value 직접 접근

• um[key]
• um.find[key] 로 찾고 .second로 접근