2-9. Repeated String Match (LeetCode 686)

---

문제 풀기 전 생각 : 

while 문으로 반복하며 스트링 타입의 변수 s를 추가해

s에 a를 계속 더하며 s에 b가 포함되어 있는지 판별하는 식으로 문제를 풀려고 했다.

반복의 종료조건은 s가 b보다 세배 이상 커지면 으로 하려고 했지만 처음부터 세배 이상 큰 a가 들어온다면

위에서 생각한 종료조건은 완벽한 종료조건이 아니다.

 

이 문제를 해결하려 a가 b보다 크다면 a에 b가 포함되는지 판변하고 한번만 더 판별하도록 했다.

그 후에도 포함되지 않는다면 그건 포함될 수 없는 케이스 라고 판별하도록 했다.

 

제출을 하자 Time Limit Exceeded 가 떴다.

그 이유를 보니 b가 굉장히 길었으며 a는 단 한글자였고

심지어 포함될 수 없는 조건이었기 때문이었다.

 

그래서 만약 a가 한글자라면 b에 a를 제외한 다른 문자가 있는지 찾아보고 있다면 -1을 리턴

없다면 b의 길이를 리턴하도록 했다.

---

 

#include <iostream>
using namespace std;

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int count = 1,flag = 0;
        string s = "";
        if(a.length() == 1 && b.find(a) != string::npos){
            for(int i = 0 ; i < 26 ; i++){
                if(b.find('a' + i) != string::npos && ('a'+i) != a[0]) {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                return b.length();
            }
        }
        else if(a.length() > b.length()){
            if(a.find(b) != string::npos) return count;
            a += a;
            count++;
            if(a.find(b) != string::npos) return count;
        }
        else 
            while(s.length() < 2*b.length() ){
                s += a;
                if(s.find(b) != string::npos)
                    return count;
                count++;
            }
        return -1;  
    }
};

https://leetcode.com/problems/repeated-string-match/

Repeated String Match - LeetCode

---

풀 때 어려웠던 점 또는 느낀점 :

생각하지 못했던 경우의 수가 등장해 당황스러웠다.

하지만 다시 발생한 오류나 경우의수를 해결할 방법을 생각하기 시작했고

얼마 지나지 않아 방법을 찾아낼 수 있었다.

 

막상 문제가 생겨 당황스러울 때는 복잡하네 쉬운 문제나 풀까? 라는 생각이 들었지만

계속해서 문제와 오류가 난 인풋을 보며 고민하니 해결되는 것을 보았다.

앞으로 당황스러운 순간이 또 찾아오면 포기하기 보다 고민해보는 것을 먼저 생각할 것이다.