상처 길이 찾기 문제

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string board[5];
bool compare(char a, char b) {
	if (a == '*' && b == '_') return true;
	if (a == '_' && b == '*') return false;
	if (a == '*') return true;
	return false;
}
int main() {
	for (int i = 0;i < 5;i++) {
		cin >> board[i];
	}
	//first board[i][0] find '#'
	
	for (int i = 0; i < 5;i++) {
		int end = board[i].length();
		sort(&board[i][0], &board[i][end], compare);
		//cout << board[i];
		int start = 0;
		if (board[i][0] == '_') {
			cout << 0 << endl;
		}
		else if (board[i][end - 1] == '*') {
			cout << end << endl;
		}
		else {
			while (1) {
				int mid = (start + end) / 2;
				if (board[i][mid] == '*' && board[i][mid + 1] == '_') {
					cout << mid + 1 << endl;
					break;
				}
				else if (board[i][mid] == '*') {
					start = mid + 1;
				}
				else {
					end = mid - 1;
				}
			}
		}
	}


}

입력 예제

__*_______________

______***_______

__**********__________

****________

******

출력 결과

1 3 10 4 6

 

 

원래 인덱스 찾아서 하는게 이상적인데

 

정렬되어 있지 않은 데이터에서 어떻게 binary search쓰는지 감이 안와서

어차피 길이 찾는 문제니까 compare함수 써서 정렬함 

ㅋㅋㅋㅋㅋㅋ

 

sort()쓰면

*_________

*****___

 

이런식이 돼서

 

그냥 right인덱스만 찾으면 됨 ><