[C++] 문자열 복사 (2195번)

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

2195번: 문자열 복사

---

문제풀이

처음에 그냥 문자열 무지성으로 비교하면 되려나? 시간 초과나지 않을까? 어떻게 푸는거야. 라는 생각을 하다가 결국 다른 사람이 어떻게 풀었나 살짝 봤다. 그런데 진짜 그냥 하나하나 비교하더라. 왜 다 비교하는데 시간초과가 안날까?

 

일단 풀이 방법을 먼저 보자.

bdx 라는 변수를 지정하고, 이 bdx가 p의 길이보다 작을 때 까지 while문을 돌린다.

이 while 문에서는, p의 앞부분부터 s와 일치하는 것중 가장 큰 길이를 찾아낸다.

한번의 반복이 끝나면, bdx 값을 일치하는 길이만큼 증가시켜 다시 거기부터 s와 일치하는 부분을 찾는다.

 

바깥 반복문에, 일치하는걸 찾는 곳에서 두번의 반복문을 써서 총 세번의 반복문을 사용한다.

근데 왜 시간 초과가 안날까?

그건 바로 탐색해야 하는 p의 길이가 계속 줄어들기 때문이다.

만약 일치하는 개수가 적다면, 3번째 반복문의 반복 횟수가 거의 1에 가깝고, 일치하는 개수가 많다면, 그만큼 다음번 비교 대상의 길이가 줄어든다. 그렇기 때문에 시간초과가 나지 않는 것이다.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    
    int answer = 0;
    int bdx = 0;
    while(bdx < b.length()) {
        int len = 0;
        for(int i=0; i<a.size(); i++) {
            int tmp = 0;
            int bdx2 = bdx;
            for(int j=i; j<a.size(); j++) {
                if(a[j] == b[bdx2] && bdx2 < b.length()) {
                    tmp++;
                    bdx2++;
                }
                else break;
            }
            // cout << tmp << endl;
            len = max(len, tmp);
        }
        // cout << endl;
        bdx = bdx + len;
        answer++;
    }

    cout << answer;
    return 0;
}