23.01.04 Today’s Leetcode

2244. Minimum Rounds to Complete All Tasks (medium)

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        counter = collections.Counter(tasks)
        res = 0
        for p in counter.values():
            # print(p)
            if p < 2:
                return -1
            else:
                res += math.ceil(p / 3)
                # divmod 를 이용하면 더 빨라지더라.
        return res     

2186. Minimum Number of Steps to Make Two Strings Anagram II (medium)

anagram : a string that contains the same characters with a different (or the same) ordering.
두 문자열을 anagram으로 만들기 위해서 최소한 몇번의 append가 필요한지 계산하는 문제이다. 처음에는 counter을 이용해서 중복되는 문자열을 카운팅하여 어떤 문자열이 필요한지 계산했다. 계산 부분에서 문제가 있는지 테스트케이스 17번에서 오류가 떴다. 그래서 다시 구현방법을 생각해봤다.

class Solution:    
    def minSteps(self, s: str, t: str) -> int:
        a, b = collections.Counter(s), collections.Counter(t)
        intersection = set(a) & set(b)
        target_a = {}
        for key in intersection:
            target_a[key] = min(a[key], b[key])
        target_b = copy.deepcopy(target_a)

        append_a, append_b = 0, 0
        for c in s:
            if c in target_a:
                if target_a[c] > 0:
                    target_a[c] -= 1
            else:
                append_a += 1
        for c in t:
            if c in target_b:
                if target_b[c] > 0:
                    target_b[c] -= 1
            else:
                append_b += 1
        # print(append_a, append_b)
        return append_a + append_b

다시 생각한 방법이 아래 방법이다. 단순하게 문자열의 개수 만 카운팅 하면 되기 때문에, 중복되는 문자열의 개수를 원래 문자열의 길이에서 빼는 방식으로 구현했다.

class Solution:    
    def minSteps(self, s: str, t: str) -> int:
        a, b = collections.Counter(s), collections.Counter(t)
        intersection = set(a) & set(b)
        # print(intersection)
        c = 0 
        for key in intersection:
            c += min(a[key], b[key])
        return len(s) + len(t) - c * 2

122. Best Time to Buy and Sell Stock II (medium, solving)

testcase 112,

class Solution:

    def dfs(self, prices, date):
        n = len(prices)
        if date >= n:
            return 0
        cur = prices[date]
        res = -1
        for i in range(date + 1, n):
            if prices[i] > cur:
                res = max(res, self.dfs(prices, i + 1) + prices[i] - cur)
        if res == -1:
            res = self.dfs(prices, date + 1)
        return res

    def maxProfit(self, prices: List[int]) -> int:
        return self.dfs(prices, 0)