[BOJ] 2866. 문자열 잘라내기

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

2866번: 문자열 잘라내기

테이블의 행을 i-1번째까지 지운 상태에서 i번째행부터의 문자열을 검사한다고 했을 때, 동일한 문자열이 있다면 그 이후 문자열들도 중복이다. 예를 들어, abc와 abc가 중복이면 이후인 bc와 bc, c와 c가 중복이기 때문이다.

반대로 중복이 아니라면 i-1번째 행까지 지웠을 때에도 중복이 아니다. 그 이전에 중복이면 위와 같은 이유로 현재도 중복일 것이기 때문이다. 

 

 

이분 탐색으로 mid번째 행부터 시작하는 문자열(mid-1번째까지는 지워진 상태)을 검사하여 동일한 문자열이 발생한다면 mid 이전의 행을 탐색하고, 만약 동일한 문자열이 발생하지 않는다면 더 큰 값을 찾기 위해 mid이후의 행을 지웠을 때의 문자열들을 검사해서 정답을 구할 수 있다. 중복이 발생하지 않은 행 중 최댓값이 count값으로 정답이 된다.

 

 

문자열의 중복을 검사할 때에는 set을 이용하였다.

 

#include <iostream>
#include <string>
#include <set>
using namespace std;
 
int r, c;
int ans;
char table[1000][1000];
 
bool check(int start, int end) {
    set<string> s;
 
    for (int j = 0; j < c; j++) {
        string tmp;
        //start행부터 마지막행까지 읽어서 문자열을 만든다.
        for (int i = start; i <= end; i++) tmp += table[i][j];
 
        //set에 문자열이 존재한다면 바로 false를 리턴한다.
        if (s.find(tmp) == s.end())
            s.insert(tmp);
        else
            return false;
    }
 
    return true;
}
 
void binarySearch(int left, int right, int end) {
    if (left > right) return;
 
    int mid = (left + right) / 2;
 
    //mid번째 행부터 마지막 행까지의 문자열을 검사
    bool flag = check(mid, end);
    
    if (flag) {
        //동일한 문자열이 발생하지 않았다면 mid이후 부분을 검사
        
        //중복이 발생하지 않은 행 중 최댓값이 정답
        if (ans < mid) ans = mid;
        binarySearch(mid + 1, right, end);
    }
    else {
        //동일한 문자열이 발생했다면 mid 이전 부분을 검사
        binarySearch(left, mid - 1, end);
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> table[i][j];
        }
    }
 
    ans = 0;
    
    //처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않음이 보장되므로 1번째 행부터 검사
    binarySearch(1, r - 1, r - 1);
    cout << ans << '\n';
 
    return 0;
}