파이썬 꿀팁

[leetcode 1592] split(), count() 이용

1592. Rearrange Spaces Between Words
문제의 명세는 쉬웠다.
단순히 문자열 중 공백(' ')을 기준으로 단어를 나누고 공백을 다시 재분배하면 된다.
다만 처음엔 파이썬이 제공하는 split(), count()를 직접 구현하려 했다.
이유인 즉, 문자열 메서드 count()의 존재를 몰랐으며, split()은 반드시 스플릿하려는 문자를 argument로 넘겨줘야 하는 줄 알았기 때문.

class Solution:
    def reorderSpaces(self, text: str) -> str:
        cnt = 0
        si = -1
        words = []
        for i, c in enumerate(text):
            if c == ' ':
                cnt += 1
                if si != -1:
                    words.append(text[si:i])
                    si = -1
            else:
                if si == -1:
                    si = i
        if text[-1] != ' ':
            words.append(text[si:])
        words_size = len(words)
        if words_size > 1: 
            q, r = divmod(cnt, len(words) - 1)
        else:
            q = 0
            r = cnt
        return (' ' * q).join(words) + ' ' * r

split()은 argument로 아무 문자도 넘겨주지 않을 경우 알아서 공백(' ')으로 스플릿을 진행하되, 여러 공백이 붙어있는 경우 하나의 공백으로 취급한다.
따라서 그냥 count()와 split()을 써 아래처럼 간단하게 작성하면 된다.

class Solution:
    def reorderSpaces(self, text: str) -> str:
        words = text.split()
        words_size = len(words)
        cnt = text.count(' ')
        
        if words_size > 1: 
            q, r = divmod(cnt, len(words) - 1)
        else:
            q = 0
            r = cnt

        return (' ' * q).join(words) + ' ' * r

[leetcode 1443] list 대신 set 이용

1443. Minimum Time to Collect All Apples in a Tree
부모-자식 관계 구분이 없는 edge 리스트를 이진트리처럼 변환하는 과정에서 Time Limit Exceeded가 발생했다.

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        def _dfs(cur_node):
            depth = 0
            for child_node in tree[cur_node]:
                depth += _dfs(child_node)
            if hasApple[cur_node] or depth:
                if cur_node:
                    depth +=  2
            return depth

        # Convert array to tree
        tree = [[] for i in range(n)]
        visited = [0]
        for _from, _to in edges:
            if _to in visited:
                tree[_to].append(_from)
            else:
                tree[_from].append(_to)
                visited.append(_to)

        return _dfs(0)

어떤 원소가 포함돼 있는지를 볼 때 평균적으로 시간복잡도가 list의 경우 O(N), set의 경우 O(1)이므로 이런 케이스에서는 set 자료형을 사용하자.

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        def _dfs(cur_node):
            depth = 0
            for child_node in tree[cur_node]:
                depth += _dfs(child_node)
            if hasApple[cur_node] or depth:
                if cur_node:
                    depth +=  2
            return depth

        # Convert array to tree
        tree = [[] for i in range(n)]
        visited = set([0])
        for _from, _to in edges:
            if _to in visited:
                tree[_to].append(_from)
            else:
                tree[_from].append(_to)
                visited.add(_to)

        return _dfs(0)

알고리즘 접근

[leetcode 452, leetcode 1288] RCI 알고리즘

452. Minimum Number of Arrows to Burst Balloons
1288. Remove Covered Intervals

from heapq import heapify, heappush, heappop


class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        cnt = 0
        inversed_points = [[x_max, x_min] for x_min, x_max in points]
        not_bursted = []
        #print(inversed_points)
        heapify(inversed_points)
        
        while inversed_points or not_bursted:
            popped = heappop(inversed_points)
            lm = popped[0]
            heappush(inversed_points, popped)
            cnt += 1

            while inversed_points:
                popped = heappop(inversed_points)
                if popped[1] <= lm <= popped[0]:
                    pass
                else:
                    heappush(not_bursted, popped)
            #print(f"lm = {lm}, not_bursted = {not_bursted}")
            inversed_points = not_bursted
            not_bursted = []

        return cnt

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])
        last_lowest_max = points[0][1]
        cnt = 1

        for each_point in points:
            if each_point[0] > last_lowest_max:
                cnt += 1
                last_lowest_max = each_point[1]

        return cnt