알고리즘 문제풀이/LeetCode

LeetCode 686번- Repeated String Match

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

 

Repeated String Match - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

class Solution {
public:
    int repeatedStringMatch(string A, string B) {      
        //1)a를 계속해서 반복 시킨다 b를 찾을때까지. 
        int count = 1;
        string plus = A;
        int flag = 0;
        while(A.size() <= plus.size() + B.size()){
            if(A.find(B) == -1){
              A += plus;
              count++;
            }
            else{
                return count;
            }
        }
        
        if(A.find(B) == -1){
           count = -1;
        }
       
        return count;
        
    }
};

처음에 정말 쉬운 문제라고 생각을 하고 접근을 했는데... Time 문제로 계속해서 고생을 했다. 

time 문제를 일으킨 원인은 바로 while문에 조건이다. 

while문을 처음에 무한 반복을 했었다. 찾으면 나오라 라고 하니 못찾을때 무한 반복이 되었다. 

그래서 다시 생각해보니, while문이 최소로 돌수 있는 조건을 생각해 내었다. 

이때  B와 A를 더한 사이즈는 A가 반복되서 길어진 스트링보다 커야 한다. 만약 이 안에 찾아내지 못하면, substring은 없는것이다. 

그 이유는 최대 b의 길이만큼 반복했을때 찾아내져야 하기 때문이다.