[BOJ] 14426번_접두사 찾기_이분 탐색 (C++)

[문제]

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

문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다.

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수를 구하는 프로그램을 작성하는 문제이다.

[사용 알고리즘]

이분 탐색

[풀이 핵심]

• 이 문제는 풀이 방법이 여러가지 있는 것 같지만 나는 이분탐색을 사용해서 해결했다.

1. 먼저 조건에 맞는 입력을 받아, v에 단어를 저장해준다.
2. 이후 이분탐색을 위해 algorithm 헤더파일의 sort 함수를 이용해서 입력받은 단어를 사전순으로 정렬해준다.
3. 그리고 M번 접두사인지 판별할 단어를 입력받고, 이분탐색을 진행한다.
   3-1. 이분탐색은 해당 단어들의 사전순을 기준으로 탐색한다. 탐색 도중 v[mid].sub(0,prefix.size())와 prefix가 같으면(word의 처음부터 prefix의 길이까지 잘랐을 때, prefix와 같다는 의미이다.) 접두사가 맞으므로 result값을 올려주고, break를 통해 탐색을 멈추면된다.

[코드]

//boj14426번_접두사 찾기_이분 탐색

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;

	vector<string> v;

	for (int i = 0; i < N; i++) {
		string word;
		cin >> word;
		v.push_back(word);
	}

	sort(v.begin(), v.end());

	int result = 0;

	for (int i = 0; i < M; i++) {
		string prefix;
		cin >> prefix;

		int start = 0;
		int end = v.size() - 1;

		while (start <= end) {
			int mid = (start + end) / 2;

			if (prefix < v[mid]) {
				end = mid - 1;
			}
			else if (prefix > v[mid]) {
				start = mid + 1;
			}

			if (v[mid].substr(0, prefix.size()) == prefix) {
				result++;
				break;
			}
		}
	}

	cout << result;

	return 0;
}