leetcode 935(dp), 503(monotonic stack), 1004(sliding window), 340(sliding window)

935 https://leetcode.com/problems/knight-dialer/
미리 다음에 갈수 있는 길들을 저장해놓는다. 그리고 n번만큼 반복해주면서 메모이제이션으로 한번 했던 계산은 하지 않도록 조절한다. 

class Solution:
    def knightDialer(self, n: int) -> int:
        #n=3131
        d = {-1: range(10), 0: [4,6], 1: [6,8], 2: [7,9], 3: [4,8], 4: [0,3,9], 5: [],
             6: [0,1,7], 7: [2,6], 8: [1,3], 9: [2,4]}
        cache = {}
        def dp(n, path):
            if n == 0:
                return 1
            key = (n, path)
            if key in cache:
                return cache[key]
            count = 0
            for _next in d[path]:
                count += dp(n-1, _next)
            cache[key] = count
            return cache[key]
        s = dp(n, -1) % (10**9+7)
        #print(cache)
        return s

근데 이게 통과는 하는데 그렇게 빠르지는 않다. 와 근데 얘는 천재인듯. 
https://leetcode.com/problems/knight-dialer/discuss/189252/O(logN) 첫번째 O(N) time, O(1) space 인 코드도 dp이긴 한데 저렇게 쉽게 풀어써버리네.. 

503 https://leetcode.com/problems/next-greater-element-ii/
바로 이전글에서 monotonic이라는 증가하는 스택을 언급했었는데 예시 문제가 바로 나왔다. 문제에 예시가 부족해서 애매한 부분을 이해하기가 힘들었다. [1,2,3,4,3]의 경우 [2,3,4,-1,4]인데 이것은 '현재 인덱스의 숫자보다 큰 숫자이면서 오른쪽에 있는 숫자를 가져오는거다.'
그러니까.. [5,4,3,2,1]이면 [-1,5,4,3,2]가 아니라 [-1,5,5,5,5]라는거다. (나같은경우 단순히 현재 인덱스의 숫자보다 더큰 최소 숫자의 인덱스를 리턴하는것으로 이해했는데 이게 아님.) 

이걸 해결하려면 [5,4,3,2,1]같은경우 한번 더 붙여서[5,4,3,2,1,5,4,3,2,1]로 만든 후에 %로 인덱스를 조정하면서 monotonic stack을 만들어서 풀면 된다.

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        len_nums = len(nums)
        ret = [-1]*len_nums
        stack = []
        for i in range(len_nums * 2):
            while stack and stack[-1][0] < nums[i % len_nums]:
                ret[stack.pop()[1]] = nums[i % len_nums]
            stack.append([nums[i % len_nums], i % len_nums])
        return ret

1004 https://leetcode.com/problems/max-consecutive-ones-iii/
아주 전형적인 슬라이딩 윈도우 문제다. k를 써서 윈도우를 최대한 넓힌 후 오른쪽으로 한칸씩 가면서 그 윈도우를 유지해준다. 그리고 매번 최대값을 갱신해준다.

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l,r = 0,0
        ret = 0
        while r < len(nums):
            if nums[r] == 0:
                if k > 0:  # k가 남아있으면 k를 쓴다.
                    k -= 1
                else:
                    while nums[l] != 0:  # l위치가 0이면 1까지 그냥 지나가준다.
                        l += 1
                    l += 1
            ret = max(ret, r-l+1)  # 최대 넓이를 매번 갱신해준다.
            r += 1
        return ret

340 https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
위와 거의 비슷하다.

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        #s="abaccc"
        #k=2
        
        l,r = 0,0
        d = {}
        ret = 0
        while r < len(s):
            d[s[r]] = r  # 현재 단어 s[r]의 최신 위치를 계속 갱신해준다.
            if len(d) > k:  # 윈도우보다 커지면 가장 처음에 삽입되었던(인덱스가 가장 앞쪽의) 문자를 뺀다. 
                            # 그리고 빠진 문자의 인덱스가 윈도우의 왼쪽이다.
                c, l = sorted(d.items(), key=lambda x: x[1])[0]  
                del d[c]
                l += 1
            ret = max(ret, r-l+1)  # 윈도우의 왼쪽과 오른쪽 길이를 잰다.
            r += 1
        return ret