[리트코드]322. Coin Change

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [1e9] * (amount + 1) dp[0] = 0 for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != 1e9 else -1 사용언어 Python3 난이도 Medium 문제풀이과정 해당 문제를 보자마자 Dynamic..아.. DP를 떠올렸다.. 가장 대중적인 DP문제라고 생각한다. 만들어야하는 값을 DP 배열로 만든다. 0은 포함하지 않기에 +1 내가 가진 코인으로 해당 값을 만드는데 최소..

[리트코드]172. Factorial Trailing Zeroes

class Solution: def trailingZeroes(self, n: int) -> int: zero = 0 if n == 0: return 0 temp = math.factorial(n) while temp % 10 == 0: zero += 1 temp //= 10 return zero 사용언어 Python3 난이도 Easy 문제풀이과정 그냥 팩토리얼 메소드로 값을 구해서 해당 문제의 조건을 만족하는 부분을 찾기위한 로직을 구현했다. 다만 엄청나게 느리다. 다른 사람들의 풀이를 보아하니 마지막이 0인 조건을 찾는 과정들로 보인다. 그냥 진짜 수학문제.. Pass 해당 문제의 좋아요가 싫어요보다 정말 조금 많다.

[리트코드]45. Jump Game II

class Solution: def jump(self, nums: List[int]) -> int: current_end = 0 jump = 0 far = 0 for i in range(len(nums)-1): far = max(far, nums[i] + i) if i == current_end: jump += 1 current_end = far return jump 난이도 Medium 그리디나 dp문제 같다는 느낌을 받으며 풀이를 시작했다. 처음 있는 곳에서 다음 곳으로 가는 것을 고를때 다다음곳으로 갈수있는 범위가 가장 큰것을 고르려했다. 허나 생각처럼 구해지지 않고 예외 케이스에 계속 걸렸기에 답을 봤다. 위의 풀이는 문제 해설에 나온 풀이다. 그리디 알고리즘으로 풀었다고 하는데 솔직히 이해는 잘 ..

[리트코드]1854. Maximum Population Year

class Solution: def maximumPopulation(self, logs: List[List[int]]) -> int: max_year = -1e9 min_year = 1e9 max_po = 0 ye = 0 for i in range(len(logs)): if min_year > logs[i][0]: min_year = logs[i][0] if max_year < logs[i][1]: max_year = logs[i][1] for i in range(min_year, max_year): cnt = 0 for j in range(len(logs)): if logs[j][0]

[리트코드]1002. Find Common Characters

from collections import Counter class Solution: def commonChars(self, words: List[str]) -> List[str]: temp = Counter(words[0]) for i in range(1, len(words)): temp &= Counter(words[i]) return temp.elements() 난이도 Easy 파이썬의 Counter함수의 교집합을 사용해서 풀어냈다.

[리트코드]740. Delete and Earn

class Solution: def deleteAndEarn(self, nums: List[int]) -> int: if not nums: return 0 freq = [0] * (max(nums)+1) for n in nums: freq[n] += n #print(freq) dp = [0] * len(freq) dp[1] = freq[1] for i in range(2, len(freq)): #print(freq[i], dp[i - 2], dp[i - 1]) dp[i] = max(freq[i] + dp[i-2], dp[i-1]) print(dp) 혼자서 풀어내지 못했다. 역시나 DP문제 나의생각방식 카운터로 모은다음에 곱해서 가장 큰 값을 기준으로 양옆보다 크면 더하고 양옆 없애버리고 아니면 그 다음 ..

[리트코드]18. 4Sum

class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: #두개 고르고 투포인터 고르고 하나를 옮김 nums.sort() ans = [] for i in range(len(nums) - 3): for j in range(i + 1, len(nums) - 2): s, e = j + 1, len(nums) - 1 while s < e: sum = nums[i] + nums[j] + nums[s] + nums[e] if sum == target: if sorted([nums[i], nums[j], nums[s], nums[e]]) not in ans: ans.append([nums[i], nums[j], nums[s]..

[리트코드]16. 3Sum Closest

class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: diff = 1e9 nums = sorted(nums) for i in range(len(nums)): s, e = i + 1, len(nums)-1 while s < e: sum = nums[i] + nums[s] + nums[e] if abs(target - sum) < abs(diff): diff = target - sum if sum < target: s += 1 else: e -= 1 if diff == 0: break return target - diff ''' 투포인터문제 정렬하고 범위 줄여가면서 계산한다. '''

[리트코드]1762. Buildings With an Ocean View

class Solution: def findBuildings(self, heights: List[int]) -> List[int]: stck = [] #비어있으면 넣고 #다음에 들어온게 더 크면 넣고 작으면 넣지 않는다. stck.append((heights[-1], len(heights)-1)) for i in range(len(heights)-1, -1, -1): if stck[-1][0] < heights[i]: stck.append((heights[i], i)) stck.sort(key = lambda x : x[1]) #print(stck) ans = [] for i in range(len(stck)): ans.append(stck[i][1]) return ans 미디움이라고 되어있지만 조금 쉬..

leetcode 5.Longest Palindromic Substring

난이도 Medium 사용언어 python3 나의 풀이는BruteForce라고 생각됨 주어지는 문자열에서 가장 긴 회문을 찾는 문제 구조를 잘 세우면 잘해보면 아주 쉽게 풀리는 문제인데 처음에 어떻게 찾아야하나 헤매다 답을 보고 깨달아 풀은문제 class Solution: def longestPalindrome(self, s: str) -> str: res = "" for i in range(len(s)): odd = self.palinSearch(s, i, i) //문자열의 글자가 홀수일 경우 even = self.palinSearch(s, i, i+1) //문자열의 글자가 짝수일 경우 res = max(odd, even, res, key=len) //max의 key 관련해서 몰랐다가 검색을 통해 알아냄..