[코딩테스트]백준17219번 비밀번호 찾기 -C++

• 백준 17219 비밀번호 찾기 문제 바로가기

문제 풀이

• 이진 탐색을 이용해서 사이트에 대한 비밀번호를 찾는 간단한 문제이다.
• 주의할 점
  1) 처음 벡터를 이용하여 문제를 풀었다. 벡터는 시간 초과가 되기 쉽다. 따라서 배열로 수정하여 다시 풀었다.
  2) cout을 이용하면 시간 초과를 유발할 수 있다. 따라서 아래와 같은 코드를 추가해주자.

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

C++ 코드

#include<iostream>
#include<stdio.h>
#include <string>
#include<algorithm>

using namespace std;

//이진탐색으로 
string find_pwd(string s, int index, pair<string, string>* s_p) {

	int l = 0;
	int mid = index / 2; 
	int r = index;

	while (l<=mid && mid <=r)
	{
		if (s.compare(s_p[mid].first) == 0) {
			return s_p[mid].second;
		}
		else if (s.compare(s_p[mid].first) < 0) {
			r = mid - 1;
			mid = (l + r) / 2;
		}
		else {
			l = mid + 1;
			mid = (l + r) / 2;
		}
	}
	


}

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

	int N; //전체 사이트 주소의 수 
	int M; //찾으려는 사이트 주소의 수 
	cin >> N >> M;

	pair<string, string> *site_pwd = new pair<string,string> [N]; 

	//사이트, 비밀번호 입력 받기 
	for (int i = 0; i < N; i++) {
		string s, p;
		cin >> s >> p;
		site_pwd[i] = make_pair(s,p);
	}

	sort(site_pwd, site_pwd+N);


	//찾고자하는 사이트 입력받기 
	for (int i = 0; i < M; i++) {
		string f;
		cin >> f;
		cout << find_pwd(f, N, site_pwd) << "\n";
	}

	return 0;
}