백준 17219번 [비밀번호 찾기](C++) -yes6686- 티스토리

백준 문제 풀이: 17219 [비밀번호 찾기]

---

문제 링크: https://www.acmicpc.net/problem/17219

문제 설명:

사이트의 주소와 비밀번호를 저장하고, 이후 입력된 주소의 비밀번호를 빠르게 찾는 프로그램을 작성해야 합니다.

입력:

• 첫째 줄에 저장된 사이트 주소의 수 n과 비밀번호를 찾으려는 사이트 주소의 수 m이 주어집니다. (1 ≤ n, m ≤ 100,000)
• 다음 n개의 줄에는 각 사이트의 주소와 비밀번호가 공백으로 구분되어 주어집니다.
• 다음 m개의 줄에는 비밀번호를 찾으려는 사이트의 주소가 주어집니다.

출력:

• 각 사이트의 비밀번호를 한 줄에 하나씩 출력합니다.

예시:

입력:
16 4
noj.am IU
acmicpc.net QQ
startlink.io OP
google.com ZZZ
naver.com PPP
daum.net AAA
en.wikipedia.org WWW
github.com TTT
stackoverflow.com RRR
youtube.com SSS
facebook.com HHH
twitter.com GGG
instagram.com FFF
tistory.com CCC
wikimedia.org DDD
gall.dcinside.com BBB
google.com
startlink.io
acmicpc.net
noj.am

출력:
ZZZ
OP
QQ
IU

---

문제 해결 코드

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

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

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

    unordered_map<string, string> passwordMap; // 사이트 주소와 비밀번호를 저장

    for (int i = 0; i < n; i++) {
        string address, password;
        cin >> address >> password;
        passwordMap[address] = password; // 주소와 비밀번호를 맵에 저장
    }

    for (int i = 0; i < m; i++) {
        string address;
        cin >> address;
        cout << passwordMap[address] << '\n'; // 주소에 해당하는 비밀번호 출력
    }

    return 0;
}

---

코드 설명

이 코드는 해시맵을 활용하여 사이트 주소와 비밀번호를 저장하고, 입력된 주소의 비밀번호를 O(1) 시간에 검색합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • unordered_map는 해시맵 기반 자료구조로, 삽입 및 검색이 평균 O(1)의 시간 복잡도를 가집니다.
• 구현 세부사항:
  • passwordMap[address] = password: 주소와 비밀번호를 저장합니다.
  • passwordMap[address]: 주소에 해당하는 비밀번호를 검색합니다.
• 시간 복잡도 분석:
  • 비밀번호 저장: O(n)
  • 비밀번호 검색: O(m)
  • 전체 시간 복잡도: O(n + m)

---

결과

코드는 입력된 사이트 주소와 비밀번호를 효율적으로 저장하고, 검색 요청에 대해 빠르게 응답합니다. 입력 크기가 최대 100,000이므로 해시맵을 활용하여 효율성을 유지합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!