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

주소 : https://denise.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F 

TISTORY

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct
{
	string address;
	string password;
}Person;

bool compare(Person a, Person b)
{
	return a.address < b.address;
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	vector<Person> p;
	Person per;
	int N, M;
	cin >> N >> M;

	for (int i = 0;i < N;i++)
	{
		cin >> per.address >> per.password;
		p.push_back(per);
	}

	sort(p.begin(), p.end(), compare);

	for (int i = 0;i < M;i++)
	{
		string search;
		cin >> search;
		int start = 0;
		int end = N - 1;
		int mid;

		while (start <= end)
		{
			mid = (start + end) / 2;
			if (search == p[mid].address)
			{
				cout << p[mid].password << '\n';
				break;
			}

			else if (search < p[mid].address)
				end = mid - 1;

			else if (search > p[mid].address)
				start = mid + 1;
		}
	}
}

마무리 : 이 문제는 map을 이용해서 풀어도 되지만 저 문제를 풀었을 때는 map을 몰라서 구조체와 벡터를 이용하여 시간 내에 비밀번호를 찾기 위해 이진 탐색을 이용하였다.