[BOJ] 2866번 : 문자열 잘라내기(C++)

문제 링크 : 백준 2866번

[문제 접근]

전부 탐색하는 방식은 최악의 경우 (1000 X 1001)/2 X 1000 이므로 대략 1억이나와 시간초과가 발생하게 된다.
따라서 나는 열 개수를 fix하고 행 인덱스를 옮기면서 이분탐색했다.

1. start = 1 , end = r로 설정해준다.
2. mid번째 행부터 끝까지 문자열에 중복이 있는지 검사한다.
3. 범위 설정
   • 중복이 있으면 mid보다 작은 행부터 시작했을 때도 중복이 있을 수 있으므로 end = mid -1
   • 중복이 없으면 행을 삭제하고 내려가야하므로 start = mid + 1
4. 탐색이 종료되었을 때 start는 중복이 있는 행인데 count는 삭제된 행의 개수이므로 중복이 있기 전 행과 삭제된 행까지만 계산해야되서 -2를 해주면 된다.

⭐️ 4번 ex)
1 - a b c
2 - a b c
3 - a b c
4 - a b c
5 - a b c

4번째부터 중복이 나타난다고 가정했을 때 start는 4이고, 3번째행을 제외했을 때 동일한 문자열이 발견되는 것이므로 3번째에서 반복을 멈추고 count를 출력한다. 따라서 count는 2이다.(1, 2 행만 삭제됨)
이걸 식으로 나타내면 start - 2이다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
int r, c;
string arr[1001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> r >> c;
    for(int i=1 ; i<=r ; i++) {
        cin >> arr[i];
    }
    int start = 1, end = r;
    while(start<=end) {
        int mid = (start+end)/2;
        set<string> s;
        bool check = true;
        for(int i=0 ; i<c ; i++) {
            string tmp = "";
            for(int j=mid ; j<=r ; j++) {
                tmp += arr[j][i];
            }
            if(s.find(tmp)==s.end()) {
                s.insert(tmp);
            } else {
                check = false;
                break;
            }
        }

        if(check) {
            start = mid+1;
        } else {
            end = mid -1;
        }
    }
    cout << start-2;
}