Bonfire

문제 나의 접근문제 요약 : 연속된 부분 배열들 중 부분 배열 내의 차이가 2보다 크지 않은 경우의 수를 모두 구하는 문제이다.제한 사항을 보니 일일이 1개짜리 배열, 2개짜리 배열 이런식으로 세다보면 시간초과 나기 딱 좋아보여서 투포인터를 생각하고 풀었다.1. 시작은 0에서 s,e 모두 시작하고, 부분배열의 최대, 최소값을 index와 값을 저장한다.2. e를 오른쪽으로 한 칸씩 움직이며, 조건에 맞도록 최대한 배열을 넓혀본다. (최대, 최소는 계속 tracking해야한다)3. 조건에 맞지않을 경우 최대한 넓혔으니, answer에 경우의수들을 더한다.4. 다음 숫자를 넣어야하므로, s를 조건을 어기게 하는 최대값 또는 최소값의 위치 다음으로 이동시켜 다음 숫자가 포함되어도 조건을 만족시키게 한다. 그..

나의 접근 방법처음에는 주어진 태그였던 스택으로 생각해보았다가, 문제를 읽으면서, dp로 풀어야겠다는 생각을 했다.문제는 다음과 같다.i 번째 과일을 사면, 그 다음에 오는 i+1 개의 과일들을 모두 공짜로 가져갈 수 있다.공짜로 가져갈 수 있는 과일들이라도, 여전히 살 수 있다.모든 과일들을 가져갈때, 최소한의 비용을 구하시오." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스내가 생각했던 논리는 다음과 같다.i+1번째 과일을 사서 모두 가져가려면, i번째까지 과일들은 i번째에 과일을 샀거나 안샀거나 중 하나이고,i+1번째 과일을 안사면서 모두 가져가려면, 이전 k번째에서 k+1개의 과일들을 가져가는 범위에 i+1번째 과일이 속해있어야 한다." data-ke-type="html..

나의 접근1. O(N)의 시간 복잡도로 nums 배열을 하나씩 체크하면서 간격 사이에 있는 숫자들을 k가 충족 될때까지 한번에 합을 구하는 방식을 사용했다.2. 시작할때 중복된 값을 제거 후 정렬을 진행하여 수가 큰 경우 낭비되는 runtime을 줄였다.3. while문 이후에 더 코드를 작성하면 더러워 보여서, 제한사항인 10**9이 끝이므로 10**9+1을 추가하여, while문으로 정답을 구할 수 있도록 작성하였다.나의 코드class Solution: def minimalKSum(self, nums: List[int], k: int) -> int: nums.append(10**9+1) nums=sorted(set(nums)) start=0 an..

나의 접근사고핵심 아이디어 : 한 점에서 다른 점으로 오름차순으로 이동하면서, 기울기가 바뀔때마다 선을 새로 그어야한다나는 고등학교 때 공부했던 단위벡터를 구해서 하려다 소수점까지 나오면 복잡해지므로, 현재와 다음 점 사이의 벡터를 구한뒤 둘의 최대공약수로 나눠 소수로 이루어진 벡터를 구하고 비교했다. 나의 코드class Solution: def minimumLines(self, stockPrices: List[List[int]]) -> int: stockPrices.sort(key=lambda x: x[0]) if len(stockPrices)==1: return 0 answer=1 def gcd(a,b): ..

Leetcode Remove K Digits기본 아이디어는 숫자를 하나씩 체크하면서 작아지는 숫자가 그 숫자보다 큰 수들을 빼면서 k값을 줄여주는 것이었다.문제를 다 풀고 다른 사람들 코드를 보고 나니 같은 코드인데 짧게 정리된 걸 보니 어떻게 저렇게 정리해서 생각할 수 있을지 궁금하다..  아직 아이디어에 비해 구현력이 부족하다는 걸 느꼈다.나의 코드import sysclass Solution: def removeKdigits(self, num: str, k: int) -> str: i=0 stack=[] sys.set_int_max_str_digits(10**5) while k>0 and i0 and stack and int(stack[-1])>..