😍 LeetCode Easy Collections III - 6 Problems

0231. Power of Two / 0118. Pascal's Triangle

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        
        if n <= 0: return False
        
        def pot(n):
            if n == 1:
                return True
            if n%2 == 1:
                return False
            
            return pot(n//2)
        
        return pot(n)

😍 0231) 큰 problem을 2로 계속 나누며 sub-problem으로 잘게 쪼개며 계속 문제를 풀어나가는 방식은 Recursion을 사용해야 함을 직관적으로 알 수 있다. 먼저 n == 1 / n%2 == 1 base case를 생각하고 / 그렇지 않다면 pot(n//2)로 잘게 쪼개어 문제를 풀어가면 OK

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1]]
        for i in range(1,numRows):
            row = []
            for j in range(0,i+1):
                if j == 0 or j == i:
                    row.append(1)
                else:
                    row.append(ans[i-1][j-1]+ans[i-1][j])
            ans.append(row)
        return ans

 

😍 0118) 공식에 맞게 dp table 채워나가면 된다.

---

0746. Min Cost Climbing Stairs / 1768. Merge Strings Alternately

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [cost[0], cost[1]]
        for i in range(2, len(cost)):
            dp.append(min(dp[-1],dp[-2])+cost[i])
        return min(dp[-1],dp[-2])

 

😍 0746) DP 문제. 각 dp의 element는 해당 element 번째의 stair를 반드시 밟았다고 했을 때의 min cost로 정의. 그러면 i번째 계단을 밟았을 때의 min cost dp[i]는 앞서 바로 앞 계단을 밟았을 때와 / 바로 두번째 앞 계단을 밟았을 때의 cost 중 최솟값에 현재 계단을 밟았을 때의 값이다. 이후 쭉 dp를 업데이트 한 후, 맨 마지막 계단을 밟았을 때 / 맨 마지막 바로 앞 계단을 밟았을 때의 cost 중 최솟값으로 정답 리턴

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        ans = ''
        for x in range(min(len(word1),len(word2))):
            ans += word1[x]
            ans += word2[x]
        if len(word1) > len(word2):
            ans += word1[len(word2):]
        elif len(word2) > len(word1):
            ans += word2[len(word1):]
        return ans

 

😍 1768) 주어진 지시사항대로 merging 진행. 단, 두 문자열의 길이가 다를 경우, 큰 문자열의 오른쪽 나머지를 붙인다.

---

1071. Greatest Common Divisor of Strings / 2215. Find the Difference of Two Arrays

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        len1, len2 = len(str1), len(str2)
        
        def valid(k):
            if len1 % k or len2 % k: 
                return False
            n1, n2 = len1 // k, len2 // k
            base = str1[:k]
            return str1 == n1 * base and str2 == n2 * base 
        
        for i in range(min(len1, len2), 0, -1):
            if valid(i):
                return str1[:i]
        return ""

 

😍 두 문자열 중 길이가 작은 문자열을 기준으로 해당 문자열 전체 문자열부터 오른쪽부터 맨 왼쪽까지 한 개씩 글자를 줄이면서 해당 문자열이 GCD 문자열인지 직접 확인

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        nums1_kind, nums2_kind = set(nums1), set(nums2)
        l,r=set(),set()
        for num in nums1:
            if num not in nums2_kind:
                l.add(num)
        for num in nums2:
            if num not in nums1_kind:
                r.add(num)
        return [list(l),list(r)]

---