[2866번] 문자열 잘라내기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 탐색

2. map STL

이 문제는 맵을 이용하여 열로 이루어진 문자열을 만들어주고 중복이 있는지 검사를 진행하는 문제이다.

이때 순차적으로 중복여부를 확인하면 TLE를 받게 되는데 이때 이분 탐색을 쓸 수 있다.

예를들어보자

6 6

qwerqy

asdbgh

zxcvbn

aceeda

abdbza

cbedqc

이 문제의 답은 2가 된다.

그 이유는 zxcvbn에서 한줄 아래를 보면 aac로 중복되는 문자열이 생성되기 때문이다.

그렇다면 aceeda부분 이 후로의 문자열은 항상 중복이 있을까? 

aceeda 아래부분부터는 ac로 중복이고 abdbza 아래부분부터는 c로 중복이다.

따라서 우리는 이분 탐색을 통해 중복이 되기 시작하는 부분을 찾아내면 된다.

중복이 나타난다면 end = mid - 1로 중복이 아직 나타나지 않았다면 start = mid + 1을 해준다.

이때 마지막 처리과정이 중요한데

만약 이분탐색 후 마지막 mid가 중복이었다면 mid - 1이 정답이 돼야하고 마지막 mid가 중복이 아니었다면 그 다음문자부터 중복이니 mid가 정답이 될 것이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <iostream> #include <cstdio> #include <map> #include <string>   #define fastio() ios::sync_with_stdio(0),cin.tie(0);   using namespace std;   string str[1002]; map<string, int> mp;   int main() {     fastio();       int n, m;     cin >> n >> m;       for (int i = 0; i < n; i++)         cin >> str[i];          int start = 0, end = n - 1;     int mid = 0;       bool trace;     while(start <= end)     {         mid = (start + end) / 2;         bool chk = true;         for (int j = 0; j < m; j++)         {             string tmp = "";             for (int i = mid; i < n; i++)                 tmp += str[i][j];                          if (mp[tmp])             {                 chk = false;                 break;             }                          mp[tmp]++;         }           if (!chk)             end = mid - 1;         else             start = mid + 1;                  trace = chk;         mp.clear();     }          if (!trace)         cout << mid - 1 << endl;     else         cout << mid << endl;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus