archives

1763 https://leetcode.com/problems/longest-nice-substring/ easy 로 분류되었는데 medium 하위정도 되는것같다. O(n^2)으로 모든 경우를 탐색한다. 길게 좌우에서 조여오면서 탐색한다. cur_s는 l과 r이 움직임에 따라 만들어지는 부분적인 문자열이고, cur_s내의 모든 문자가 대문자와 소문자가 cur_s내에 존재해야 하면서 이게 이전 길이보다 더 길면 바꿔준다. class Solution: def longestNiceSubstring(self, s: str) -> str: len_s = len(s) l = 0 ret = '' while l < len_s: r = len_s - 1 while l < r: cur_s = s[l:r+1] if all(..

974 https://leetcode.com/problems/subarray-sums-divisible-by-k/ subarray의 합이 k로 나눠지는 subarray를 구해야하는데 인덱스와 상관없이 구하는게 아니라 근처의 값들로만 구성해야 해서 백트래킹같은게 아니다. 앞에서부터 prefix sum을 계산해주며 prefix sum이 k로 나눠지면 그 값이 존재하는만큼 더해준다. 그리고 뒤에서도 사용하기 위해 그 값이 나온만큼 증가시켜준다. class Solution: def subarraysDivByK(self, nums: List[int], k: int) -> int: ret = 0 d = {0: 1} prefix_sum = 0 for i in range(len(nums)): prefix_sum += ..