잡담.
신박한 DP 문제.(kmp라 볼 수도 있는지는 모르겠다.) 워낙 오늘은 coding test에 대한 포스팅을 할 예정이 없었으나 공유하기에 좋은 문제라 생각되서 포스팅을 하게 되었다.
문제 설명.
string s가 주어질 때 주어진 두 방법에 의해 s의 길이를 0으로 만드는 최대 횟수를 구하는 문제.
그리고 그 방법은 다음과 같다.
s를 그대로 지운다.- 처음부터
i번째까지의s의 부분문자열s'이s의 시작부분이s's'이 될 때s에s'을 지운다.
example을 생각해보자.
초기 s를 "aaabaab"라고 하면, 규칙 2에 의해 s' == "a"가 될 수 있다.
step1 : s = "aabaab"
다음으로 규칙 2에 의해 s'은 각각 "a"와 "aab"가 될 수 있다.
이 때 s'이 "a"가 될 경우 더이상 반복되는 구간이 없기 때문에 규칙 1에 의해 s를 지우게 되는 길이는 3이 된다.
이제 s' == "aab"인 경우를 살펴보면,
step2 : s = "aab"
step3 : s = "ab" (s' = "a" )
steo4 : s = ""
따라서 최종 결과값은 4가 나오게 된다.
풀이 방법.
배열 dp는 s의 길이 leng만큼 0을 가진 배열로 생성하고 초기에 한번에 지우는 방법이 존재하기 때문에 dp[0] = 1로 변경해준다. 이후 for문을 이용해서 i번째 수에 대해 다음과 같은 판단을 한다.
- 만약
dp[i] == 0일 경우 앞선 결과에서s[i:]가 만들어지는 일이 없기 때문에 loop를 넘긴다. - 아닐 경우
sc = s[i:]를 만들어준다. 그다음sc의 길이 반쪽까지for문을 이용해서j번째 수에 대해sc[:2*j] == sc[:j]*2, 즉,sc[:j]가sc안쪽에서 두번 반복되서 나오는지를 체크하고, 그럴 경우
i+j번째 숫자를i번째 숫자+1과 비교해서 큰 수로 바꿔준다.
최종적으로 dp의 최댓값을 반환한다.
이 때 dp의 최댓값을 반환하는 경우는, 다음과 같은 케이스(abaaa)가 있고, 이경우 지울 수 있는 방법이 유일하기 때문에 dp의 마지막이 0이 되기 때문이다.(또한 dp[0] = 1을 넣은 시점에서 s를 지우는 모든 방법이 들어가는 것을 성립하게 만들었기 때문이다.)
풀이 코드.
class Solution:
def deleteString(self, s: str) -> int:
if len(set(s)) == 1:
return len(s)
leng = len(s)
dp = [0 for _ in range(leng)]
leng2 = len(s)
dp[0] = 1
for i in range(leng):
if not dp[i]:
continue
sc = s[i:]
for j in range(1,leng2//2+1):
if sc[:2*j] == sc[:j]*2:
dp[i+j] = max(dp[i]+1,dp[i+j])
leng2 -= 1
return max(dp)추가.
3,4번째 줄의 경우 다음과 같은 케이스가 존재하는데 이경우 시간 초과가 떠서 넣어준 코드이다.(s="a"*4000. 3,4번째 줄이 없어도, 시간이 걸리긴 하지만 답 자체는 잘 나온다.)
error.
s = "a"*3999+"b"에 TLE가 나온다. substring 비교를 O(1)의 시간 으로 해야한다고 하는데 흠....
