Problem Solutionsliding window 연속된 3개 숫자를 뒤집어서 모두 1로 바꿀 수 있는 최소한의 횟수를 구하는 문제.당연히 2중포문을 쓰면 시간초과가 발생한다.n-2까지만 검사해서 nums[i] == 0 이면 i ~ i+2까지 비트연산으로 1, 0을 뒤집는다.연산이 끝나면 answer+=1비트연산 파이선으로 ^= 이더라? 괜히 if~else 구문으로 바꾸고있었네 마지막에 2개숫자가 0이면 연속된 3자리가 아니라 못바꾸므로 바로 리턴 -1아니면 answer return Codeclass Solution: def minOperations(self, nums: List[int]) -> int: n = len(nums) ans = 0 for i i..

Problem SolutiondbLCS (Longest Common Subsequence)이 문제의 힌트를 보고 LCS 알고리즘을 사용한 문제라는 것을 알았다.LCS 알고리즘에 대한 설명은 다른 블로그에서 더 자세하게 설명해두어서 참고했다!https://chanhuiseok.github.io/posts/algo-34/ 알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘LCS 알고리즘이란?chanhuiseok.github.io 단 LCS 의 길이를 구하는 알고리즘이라서 LCS 문자를 찾으려면 역추적(back tracking)을 이용해서 구해야한다. 주어진 2개의 string의 LCS 를 구하는 규칙은 아래와 같다.문자열을 비교하여 같았을 때현재 칸에 들어..

Problem SolutionKadane's algorithmsubArray 중 절대값 합의 최대값을 구하는 문제.2중포문으로 구현하면 당연히 time limit 이 발생한다.힌트 중에서 Kadane's 알고리즘을 사용하라고한다. 알아보았더니 dp 문제였다.Kadane's 알고리즘을 간략히 설명하면일반적인 Kadane’s Algorithm은 최대 연속 부분합을 구하는 알고리즘입니다.여기서는 최대 합과 최소 합을 동시에 추적하여, 그 절댓값 중 가장 큰 값을 반환하도록 변경합니다.현재까지의 max_sum/min_sum 을 현재 num과 비교하며 갱신한다.Kadane's 알고리즘 설명은 다른 블로그 설명을 참고했다.https://scavienger.tistory.com/19 [Algorithm] Kadane..

Problem Solutionstringpart에 해당하는 문자가 s 에 존재하지 않을 때까지 제거하는 문제.왜 replace를 생각하지 못했을까 ㅜㅜ class Solution: def removeOccurrences(self, s: str, part: str) -> str: while part in s: s = s.replace(part,"",1) return s시간복잡도 : O(N) , 최악의 경우 O(N^2)공간복잡도: O(N)Codeclass Solution: def removeOccurrences(self, s: str, part: str) -> str: idx = 0 n = len(part) whil..

ProblemSolutionHashMapi bad pair 정의 if i bad pair의 쌍 개수 구하기관점을 바꿔서 i - nums[i] == j - nums[j] 인 good pairs를 구한 뒤 전체 - good pairs를 구한다.즉, nums[i] - i 값이 동일한 숫자끼리 good pair가 된다.그러므로, 특정 값 key = nums[i] - i를 기준으로 그룹을 만들고, 동일한 값이 등장할 때마다 good pair를 세면, 전체 쌍에서 빼서 bad pair를 구할 수 있다. 아래는 처음에 2중 for문으로 bruteforce로 풀었다가 time out 이 발생했던 코드..ㅠㅠ# solve 1)class Solution: def countBadPairs(self, nums: List..

ProblemSolutionsliding window이전 문제와 유사하게 sub array 중 오름차순이면서 총 원소합의 최대값을 구하는 문제.num array 가 100 이하라서 2중 포문을 사용해되지만 최대한 fot문을 1번만 사용하려고했다. 강력한 힌트는 The end of each ascending subarray will be the start of the nextsubarray 만들고 체크한 마지막 인덱스가 다음 순회 인덱스의 첫번째 인덱스가 된다. 아래 코드에서 idx 가 그 역할. 아래는 더 깔끔한 코드가있어서 가져와봤다.아예 처음부터 처음 0번째 값을 넣은 리스트를 선언 후 증가하는 값이 나올때마다 리스트에 추가 (cur list)작아지는 숫자가 나오면 max 값 구하고 다시 cur li..