LeetCode 2430

dombe·2022년 10월 4일
0

Coding Test(Python)

목록 보기
36/44

문제 링크

잡담.

신박한 DP 문제.(kmp라 볼 수도 있는지는 모르겠다.) 워낙 오늘은 coding test에 대한 포스팅을 할 예정이 없었으나 공유하기에 좋은 문제라 생각되서 포스팅을 하게 되었다.

문제 설명.

string s가 주어질 때 주어진 두 방법에 의해 s의 길이를 0으로 만드는 최대 횟수를 구하는 문제.

그리고 그 방법은 다음과 같다.

  1. s를 그대로 지운다.
  2. 처음부터 i번째까지의 s의 부분문자열 s's의 시작부분이 s's'이 될 때 ss'을 지운다.

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가 나오게 된다.


풀이 방법.

배열 dps의 길이 leng만큼 0을 가진 배열로 생성하고 초기에 한번에 지우는 방법이 존재하기 때문에 dp[0] = 1로 변경해준다. 이후 for문을 이용해서 i번째 수에 대해 다음과 같은 판단을 한다.

  1. 만약 dp[i] == 0일 경우 앞선 결과에서 s[i:]가 만들어지는 일이 없기 때문에 loop를 넘긴다.
  2. 아닐 경우 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)의 시간 으로 해야한다고 하는데 흠....

profile
다양한 분야에 관심이 많은 초보 개발자 입니다.

0개의 댓글