[백준/BOJ] 백준 2866번 : 문자열 잘라내기

www.acmicpc.net/problem/2866

2866번: 문자열 잘라내기

이분 탐색을 이용해 문제를 해결했다. mid행부터 시작해서 만들어지는 문자열에 중복되는 게 있는지 없는지를 판단하였다.

 

코드

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

int r, c;
vector<string> board;

bool Check(int point)
{
	set<string> col_string;
	set<string>::iterator it;

	for (int j = 0; j < c; j++)
	{
		string maked_string = "";

		for (int i = point; i < r; i++) //point행부터 시작해서 만들어지는 문자열
		{
			maked_string += board[i][j];
		}

		it = col_string.lower_bound(maked_string);
		if (it == col_string.end() || (*it) != maked_string) //이전에 없던 문자열일때
			col_string.insert(maked_string);

		else
			return false; //동일한 문자열이 발견될때
	}

	return true; //동일한 문자열이 발견되지 않을때
}

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

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	int left = 0;
	int right = r - 1;
	int result = 0;

	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (Check(mid) == true) //mid행부터 시작해서 만들어지는 문자열에 중복되는게 없을때
		{
			result = mid;
			left = mid + 1;
		}

		else
			right = mid - 1;
	}

	cout << result;

	return 0;
}