41. UVa-10567 //Binary Search

문제

<그림1: 문제 설명>

문제가 조금 이해안될 수도 있는데 Sample Input과 Output이 나오게 된 근거는 다음<그림2>와 같다.

<그림2: 문제의 예시와 그 답이 나온 근거>

Query에 있는 모든 character를 처음 INPUT에서 부분수열처럼 따올 수 있으면 matched, 아니면 not matched이다.

푸는 건 A..Z a..z총 52개의 character에 대해 52개의 vector를 사용하여 처음에 주어지는 S의 각 문자별로 그 인덱스 목록을 오름차순으로 정렬한 다음, 주어지는 Query에 대해 해당 문자의 위치를 해당 문자의 vector에서 이진탐색으로 찾는 코드를 짰다. 다만 내 코드는 이진탐색의 basis case처리가 난잡할 수 있다. basis case를 두개로 잡았으니까..

다음은 코드다.

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

vector<int> idxs[52];



int indexing(char c) {
	if (c <= 90) {
		return (c - 65);
	}
	else
		return (c - 71);
}
/*ASCII Code
A~Z: 65~90
a~z: 97~122

*/


//lowerbound'이상'이면 가능!
int BinarySearch(int s, int e,int lowerBound, char ch) {
	//실패하면 -2 반환하기
	//성공하면 idx반환하기
	int mid = (s + e) / 2;
	if (e <= s) {//size가 2만 되어도 이런 문제는 생길 일이 없음
		if (e == s) {
			if (lowerBound <= idxs[indexing(ch)][e]) return idxs[indexing(ch)][e];
			else return (-2);
		}
		else return (-2);
	}
	else if (s + 1 == e) {//mid가 움직여도 동일한 작업이 계속 반복되는 basis case.
		if (idxs[indexing(ch)][e] < lowerBound) { //절대로 해가 안 나오는 경우
			return (-2);	//-1: 해가 없음
		}
		else if (idxs[indexing(ch)][s] >= lowerBound) { //s가 해
			return idxs[indexing(ch)][s];
		}
		else {
			return idxs[indexing(ch)][e];
		}

	}
	else {
		if (idxs[indexing(ch)][mid]>=lowerBound) { //지금보는 값이 큰 경우, mid위쪽은 그것보다 더 큰 값이므로 더이상 볼 필요가 없다.
			return BinarySearch(s, mid, lowerBound, ch);
		}
		else { //지금보는 mid가 lowerbound보다 작은 경우, mid아래쪽은 그것보다 작은 값이므로 더 이상 볼 필요가 없다.
			return BinarySearch(mid, e, lowerBound, ch);
		}
	}

	//함수에서 반환된 값+1은 새로운 lowerbound로 사용된다.
}



int main() {
	string C; int Q;
	cin >> C;
	//C를 보며 각 문자의 index를 각 vector에 오름차순으로 정리
	int idx = 0;
	for (string::iterator it = C.begin(); it != C.end(); it++) {
		idxs[indexing(*it)].push_back(idx++);
	}

	cin >> Q;
	int lowerbound; //Restricted index
	int startIdx=-1,EndIdx=-1;
	bool nonsol = false;
	string Query;
	while (Q--) { // Query처리 루틴
		nonsol = false;
		lowerbound = 0;
		cin >> Query;
		//Query의 길이가 1인 경우를 따로 처리하겠음
		if (Query.size() == 1) {
			string::iterator it = Query.begin();
			lowerbound = BinarySearch(0, idxs[indexing(*it)].size() - 1, lowerbound, *it) + 1;
			if (lowerbound == -1) {
				nonsol = true;
			}
			EndIdx=startIdx = lowerbound - 1;
		}
		else {
			for (string::iterator it = Query.begin(); it != Query.end(); it++) {
				//*it: 이번의 query, Queryidx: Query의 index. 따라서
				if (it == Query.begin()) { //처음 질의는 따로 처리
					lowerbound = BinarySearch(0, idxs[indexing(*it)].size() - 1, lowerbound, *it) + 1;
					startIdx = lowerbound - 1;
					if (lowerbound == -1) {
						nonsol = true;
						break;
					}
				}
				else if (it == --Query.end()) { //마지막 질의도 따로 처리, 값을 보관해야하기 때문
					lowerbound = BinarySearch(0, idxs[indexing(*it)].size() - 1, lowerbound, *it) + 1;
					EndIdx = lowerbound - 1;
					if (lowerbound == -1) {
						nonsol = true;
						break;
					}

				}
				else {
					lowerbound = BinarySearch(0, idxs[indexing(*it)].size() - 1, lowerbound, *it) + 1;
					if (lowerbound == -1) {
						nonsol = true;
						break;
					}
				}


			}
		}




		if (nonsol) cout << "Not matched" << endl;
		else cout << "Matched " << startIdx << " " << EndIdx << endl;
	}

	return 0;
}