Problem : https://leetcode.com/problems/count-ways-to-build-good-strings Difficulty : Medium Status : Solved Time : 00:04:21  문제 설명 더보기zero, one, low, high 정수가 주어질 때, 우리는 빈 문자열에서 시작하여 문자열을 만들 수 있으며,각 단계에서 둘 중 하나를 수행한다. * '0' 문자를 zero번 반복해서 추가한다.* '1' 문자를 one번 반복해서 추가한다. 이 작업은 몇 번이고 수행될 수 있다.좋은 문자열은, 위의 작업으로 구성된 문자열이 low, high 사이의 길이(경계 포함)를 가졌을 때의 문자열이다.이 조건을 만족하는 서로 다른 좋은 문자열의 개수를 구하여라, 값이 매우 클..

Problem : https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/ Difficulty : Medium Status : Solved Time : 00:00:00 풀이 간단하긴 한데, 어떻게 더 최적화할지를 생각해보게 되는 문제. 기본적으로는 딕셔너리를 사용하여 distinct한 숫자를 관리하면 된다. k개의 fix된 길이니 슬라이딩 윈도우를 수행하며 조건에 맞을 때마다 정답을 갱신하면 되겠다. 워낙 많이 보이는 타입의 문제다 보니, 최적화가 역시 관건이 될 것 같다. 풀이코드class Solution: def maximumSubarraySum(self, nums: List[int], k: in..

Problem : https://leetcode.com/problems/defuse-the-bomb Difficulty : Easy Status : Solved Time : 00:06:22  문제 설명  풀이 슬라이딩 윈도우 문제. k가 주어진 세 가지 경우일 때를 각각 구현하면 쉽게 풀린다. 시간복잡도는 O(N). 풀이 코드class Solution: def decrypt(self, code: List[int], k: int) -> List[int]: n = len(code) result = [0]*n if k == 0 : return result if k > 0 : result[0] = sum..

Problem : https://leetcode.com/problems/find-the-power-of-k-size-subarrays-i Difficulty : Medium Status : Solved Time : ??:??:?? 풀이 어떻게 문제를 분류해 볼 수 있을까.. 싶은 문제. 연속 숫자로 sort된 길이를 임시로 저장해가며, 그 길이가 k 이상이면 그 인덱스의 숫자를 (maximum 값이 현재 index임이 충족된다), 그렇지 않다면 -1을 담아 반환하기만 하면 된다. 기본적인 sort 개념을 어떻게 응용해 볼 수 있을까를 물어보는 문제라고 생각한다. 풀이 코드class Solution: def resultsArray(self, nums: List[int], k: int) -> List[int..

Problem : https://leetcode.com/problems/minimized-maximum-of-products-distributed-to-any-store/ Difficulty : Medium Status : Solved Time : ??:??:?? 풀이 헤매고 헤매다가 힌트 하나를 보고 깨달은 문제. binary search의 응용 문제이다. 임의의 수 m에 대해서 모든 product를 m 이하가 되도록 나눌때, 이 product의 총 개수가 n이하인지를 검사하면 된다. 이를 기준으로 binary search를 수행해 최소가 되는 m(즉 lower bound)를 찾는 게 목표가 되겠다class Solution: def check(self, n, quantities, target): res..

Problem : https://leetcode.com/problems/count-the-number-of-fair-pairs Difficulty : Medium Status : Solved Time : ??:??:?? 풀이 모바일로 풀어 보는 경우를 생각해서 탬플릿을 단순화해야할까? 싶다. 각설하고, 처음 접근법은 binary search로 풀어보자고 생각했다. lower bound와 upper bound는 O(logN)시간복잡도로 구할 수 있고, 하나의 인자를 고정한 체로 다른 인자에 대해 lower bound와 upper bound를 구할 수 있기 때문이다. 이를테면, lower