[BaekJoon 17219][⚪4] 비밀번호 찾기

❓ 문제

백준 17219 - “비밀번호 찾기”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (해시 맵)

- 알고리즘

• Data Structure, Set & Map, Hashing

- 설명

unordered_map을 이용하는 풀이이다.

unordered_map 컨테이너에 사이트의 주소를 Key로, 비밀번호를 Value로 저장해 원하는 값을 O(1)의 속도로 출력하는 방식이다.

한가지 주목할 점은 emplace를 써서 값을 넣어줄 때 move를 썼는데, 이렇게 하면 값을 복사가 아닌 이동시킴으로써 더 빠르게 값을 넣을 수 있게 해준다. vector의 emplace_back과 같은 원리로, 앞으로도 이렇게 써주도록 하자.

unordered_map의 경우 삽입, 삭제, 탐색의 속도가 O(1)이므로 전체적인 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <unordered_map>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{}, iM{};
    cin >> iN >> iM;

    unordered_map<string, string> umapPassword{};
    umapPassword.reserve(iN);   // 수십만개의 케이스 정도는 max_load_factor 불필요

    while(iN--)
    {
        string strSite{}, strPW{};
        cin >> strSite >> strPW;

        // move를 써서 복사 방지 -> 더 빠름
        umapPassword.emplace(move(strSite), move(strPW));
    }

    // 출력 최적화
    string strOut{};
    strOut.reserve(iM * 21);

    while(iM--)
    {
        string strFind{};
        cin >> strFind;

        strOut += umapPassword.at(strFind); // umapPassword[strFind]보다 안전
        strOut.push_back('\n'); // 문자 하나만 넣을 땐 += 보다 push_back -> 오버로딩된 함수 호출 방지
    }

    cout << strOut;

    return 0;
}

---

💭 후기

여기서 unordered_map을 쓸 때 reserve만 하고 max_load_factor는 조절해주지 않았는데, 이는 테스트 케이스가 수백만 ~ 수천만의 경우에는 효과가 있을지는 몰라도, 이런 문제의 경우에는 오히려 캐시 친화성만 떨어트릴 수 있기 때문이다.

또한 emplace의 경우 move를 써서 값의 복사 대신 이동을 해준다던가, string을 통한 출력 최적화에서 문자 하나를 붙일 때는 push_back으로 임시 객체 생성을 방지한다던가 하는 식의 자잘한 최적화도 신경을 써주면 좋다.