leetcode.com/problems/repeated-string-match/
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의 길이만큼 반복했을때 찾아내져야 하기 때문이다.
'알고리즘 문제풀이 > LeetCode' 카테고리의 다른 글
LeetCode 844번 - Backspace String Compare (0) | 2020.07.30 |
---|---|
LeetCode 13번 - Roman to Integer (0) | 2020.07.28 |
LeetCode 67번 - Add Binary (0) | 2020.07.28 |
LeetCode 14번 - Longest Common Prefix (0) | 2020.07.28 |
LeetCode 81번 - Search in Rotated Sorted Array II (0) | 2020.07.27 |