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

문제

[C++] 백준 17219: 비밀번호 찾기 SILVER 4
https://www.acmicpc.net/problem/17219

 

---

 

접근 방법

이 문제는 사이트 주소가 주어졌을 때 해당 비밀번호를 빠르게 찾아 출력하는 문제다.
핵심은 “탐색 속도”다.

 

처음에는 vector에 (사이트, 비밀번호) 쌍을 저장해 두고, 질문이 들어올 때마다 처음부터 끝까지 순회하며 찾는 방식으로 구현했다.
하지만 이 방식은 매 질의마다 선형 탐색(O(N))이 필요해서, 입력 크기가 커지면 결국 시간 초과가 발생한다.

 

그래서 접근 방식을 바꿔, 키를 기준으로 바로 값을 찾을 수 있는 자료구조를 사용해야겠다고 판단했다.
여기서 사용한 것이 바로 map이다.

 

map을 사용한 풀이 아이디어

map은

• key → value 형태로 데이터를 저장하고
• key를 기준으로 빠르게 탐색할 수 있는 자료구조다.

이 문제에서는 아래로 딱 맞아떨어진다.

• key : 사이트 주소
• value : 비밀번호

 

1. 사이트 정보 저장

사이트 주소를 key로, 비밀번호를 value로 저장해 두면 중복 없이 깔끔하게 관리할 수 있다.

map<string, string> file;

for (int i = 0; i < n; i++)
{
    string str1, str2;
    cin >> str1 >> str2;
    file[str1] = str2;
}

 

2. 비밀번호 조회

file[str]처럼 접근하면 해당 사이트의 비밀번호를 바로 얻을 수 있다.
따로 반복문으로 찾을 필요가 없다.

for (int i = 0; i < m; i++)
{
    string str;
    cin >> str;
    cout << file[str] << '\n';
}

 

구현 시 주의할 점

• vector + 브루트포스 탐색은 입력이 커지면 금방 한계에 부딪힌다.
  → “탐색이 많이 일어나는 문제”인지 먼저 판단하는 게 중요하다.
• map은 내부적으로 정렬된 트리 구조를 사용해 삽입과 탐색이 모두 O(log N)으로 동작한다.
• 문자열을 key로 사용하는 문제에서는 map이나 unordered_map이 굉장히 강력한 도구가 된다.
• 이번 문제는 map을 처음 써보기에 딱 좋은 예제였다!

 

---

 

코드

#include <iostream>
#include <map>
using namespace std;

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

	int n = 0, m = 0;
	cin >> n >> m;

	map<string, string> file;
	for (int i = 0; i < n; i++)
	{
		string str1, str2;
		cin >> str1 >> str2;

		file[str1] = str2;
	}
	for (int i = 0; i < m; i++)
	{
		string str;
		cin >> str;

		cout << file[str] << '\n';
	}

	return 0;
}