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

1. 문제이해

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

17219번: 비밀번호 찾기

저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과

비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다.

두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어지고,

그 다음 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 주어진다.

 

이때, 비밀번호를 찾으려는 사이트 주소의 비밀번호를 찾아 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

사이트의 주소와 비밀번호를 받아 한꺼번에 저장하고,

사이트의 주소(key)를 이용해 비밀번호(value)를 찾아야 하는 문제로, 전형적인 map 문제이다.

 

map에 대한 설명과 여러 예제들은 이전에 다룬 문제들이 많으니, 아래 링크를 참고하도록 하자.

https://beginnerdeveloper-lit.tistory.com/search/map

초보 개발자의 이야기, 릿허브

 

map 에 대해 한번 더 개념을 짚고 넘어가자면 아래와 같다.

 

map은 key와 value가 쌍으로 저장되는 컨테이너로, 노드 기반의 균형 이진트리 구조를 가진다.

입력시, key는 고유한 값으로 중복이 불가능하며, key값을 기준으로 자동으로 오름차순 정렬된다.

map container는 아래와 같은 형태로 선언한다.

map< [Data type1], [Data type2] > [변수이름];

map에 대한 자세한 설명은 아래 블로그에서 잘 설명해주셨으니, 참고하도록 하자.

https://blockdmask.tistory.com/87

[C++] map container 정리 및 사용법

 

 

 

3. 소스코드

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


int main() {
	int N;	// 저장된 사이트 주소의 수
	int M;	// 비밀번호를 찾으려는 사이트 주소의 수
	string site, password;	// 사이트의 주소와 패스워드를 입력받기 위한 변수
	map <string, string> password_list;	// site, password를 저장하기 위한 map
	map <string, string> ::iterator it;	// site를 이용해 password를 찾기 위한 iterator

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	// map에 site, password list 저장
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> site;
		cin >> password;
		password_list.insert({ site,password });
	}

	// site를 입력받고, 해당 site를 이용해 password를 찾아 출력
	for (int i = 0; i < M; i++) {
		cin >> site;
		
		it = password_list.find(site);
		cout << it->second << "\n";
	}

	return 0;
}

위에서 언급했듯, map container를 이용하면 간단히 해결 가능한 문제이다.

N, M, 각 사이트와 비밀번호를 입력받아 map에 저장(insert)하고

가장 아래쪽의 for문을 이용해 site(key)를 입력받아 이와 대응되는 password를 찾아 출력한다.

 

어렵지 않은 문제이지만, 한 가지 주의해야 할 점은

cin.tie(NULL); , ios::sync_with_stdio(false); 를 꼭 넣어줘야 한다는 것과

endl 대신 \n를 사용해야한다는 것이다.

(C++은 cin, cout 시간이 오래 걸리므로 해당 구문이 필수이다.)

 

 

주석 없는 코드는 왼쪽 아래 더보기를 참고바랍니다.😊

<주석 없는 코드>

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


int main() {
	int N;
	int M;	
	string site, password;	
	map <string, string> password_list;	
	map <string, string> ::iterator it;	

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> site;
		cin >> password;
		password_list.insert({ site,password });
	}

	for (int i = 0; i < M; i++) {
		cin >> site;
		
		it = password_list.find(site);
		cout << it->second << "\n";
	}

	return 0;
}

 

 

---