leetcode 1209(stack), 1048(dp), 1854(그리디, 범위내 최대값)

1209 https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/
딱봐도 스택문제다. 새 문자가 들어올때마다 새 문자와, 새 문자가 존재하는 갯수를 넣어두고, 동일한 문자가 들어오면 카운트를 증가시켜준다. 이후 마지막 문자가 k보다 큰 경우 연산을 해준다.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        #s = "deeedbbcccbdaa"
        #k = 3
        ret = ''
        stack = []
        for i in range(len(s)):
            if stack and s[i] == stack[-1][0]:  # 이미 들어왔던 문자의 경우 카운트를 늘려준다.
                stack[-1][1] += 1
            else:
                stack.append([s[i], 1])  # 문자가 들어올 경우 해당 문자와, 해당 문자의 카운트를 넣어준다.
            while stack and stack[-1][1] >= k:  # 마지막 문자가 k개 이상이면
                if stack[-1][1] % k == 0:  # k로 나눠떨어지면 없애버리면 된다.
                    stack.pop()
                else:  # k로 나눠떨어지지 않으면 나머지만큼 남겨둔다.
                    stack[-1][1] %= k
        #print(stack)
        return ''.join([s[0]*s[1] for s in stack])

1048 https://leetcode.com/problems/longest-string-chain/
처음엔 bfs, dfs로 풀었다. words = ["a","b","ba","bca","bda","bdca"] 인 경우에 a -> ba -> bda -> bdca로 가는게 답인데 이 순서대로 구현하라고 하면 복잡하니 반대로 bdca -> bda -> ba -> a순서로 가도록 구현하면 쉽게 된다.
근데 bfs dfs는 속도가 별로 안 빠르다.

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        wordlist = set(words)
        queue = [[w, 1, set()] for w in words]
        ret = -1
        while queue:
            word, count, visited = queue.pop(0)
            ret = max(ret, count)
            for i in range(len(word)):
                new_word = word[:i] + word[i+1:]
                if new_word not in wordlist or new_word in visited:
                    continue
                visited.add(new_word)
                queue.append([new_word, count+1, visited])
        return ret

그래서 찾아봤는데 길이가 짧은 순으로 정렬한 후에 이전에 계산했던 값보다 긴 경우(답이 가장 긴 경우를 찾는거니)에만 연산을 진행하도록 하니 시간이 더 짧아진다.

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words = sorted(words, key=lambda x:len(x))
        dp = {}
        for i in range(len(words)):
            dp[words[i]] = 1
            for j in range(len(words[i])):
                predecessor = words[i][:j] + words[i][j+1:]
                # predecessor가 계산되어 있는 경우만 새연산을 하는 이유는 계산이 안되어 있으면 어차피 가장 짧은 경우이기 때문이다. 
                # 두번째 조건인 dp[word] < dp[predecessor] + 1 도 마찬가지. dp[word]가 더 짧으면 가장 긴 경우를 구하는 경우이기 때문에 의미없다.
                if predecessor in dp and dp[words[i]] < dp[predecessor] + 1:
                    dp[words[i]] = dp[predecessor] + 1
        return max(dp.values())

1854 https://leetcode.com/problems/maximum-population-year/
easy문제이고 푸는건 간단하다. 그런데 1950~2050년을 무식하게 반복하지 않고 풀수 있는 좋은 방법론을 봐서 적어놓는다. https://leetcode.com/problems/maximum-population-year/discuss/1199494/Python-sorting-max-overlapping-segments-algorithm 에 있는건데. 코드는 아래와 같고 아래와 비슷한 문제가 많은데 그런 상황들에서도 많이 쓸수있을것같다.

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        dates = []
        for birth, death in logs:
            dates.append((birth, 1))  # 태어난 날과 1을 같이 저장해둔다.
            dates.append((death, -1))  # 죽은 날과 -1을 같이 저장해둔다.
            
        dates.sort()  # 태어난,죽은 날짜를 오름차순으로 정렬한다.
        population = max_population = max_year = 0
        for year, change in dates:
            population += change  # population에 위에서 태어난 날, 죽은 날과 같이 저장해둔 1 또는 -1을 더한다.
            if population > max_population:  # 위의 과정을 반복하면 자동적으로 특정 연도에 최대 인구가 되는 시점을 알수있다..
                max_population = population
                max_year = year
        
        return max_year