Minystory

[LeetCode 236] Lowest Common Ancestor of a Binary Tree (Python)

September 1, 2022
Algorithm, LeetCode
Algorithm, Problem Solving, LeetCode, LeetCode Medium Python, Recursion

문제 링크 #

문제 해설 #

Idea #

  • root부터 조건을 만족하는 깊이까지 재귀적으로 자식 노드를 탐색하면서
    p 또는 q 노드를 발견한 경우 해당 노드를 호출한 함수에게 반환
  • 최종적으로 좌,우에 각각 p와 q가 있을 경우 깊이가 가장 깊은 부모 노드를 반환하고,
    한쪽 방향에 p와 q가 몰려있을 경우 둘 중 부모 관계에 있는 노드를 반환

Time Complexity #

  • O(N) = 10^5

Data Size #

  • nodes: [2, 10^5]
  • val: -10^9 <= int <= 10^9

해설 코드 #

python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """

        if root:
            if root == p or root == q:
                return root

            left = self.lowestCommonAncestor(root.left, p, q)
            right = self.lowestCommonAncestor(root.right, p, q)

            if left and right:
                return root
            return left if left else right

[LeetCode 1337] The K Weakest Rows in a Matrix (Python)

March 27, 2022
Algorithm, LeetCode
Algorithm, Problem Solving, LeetCode, LeetCode Easy, Python, Sorting

문제 링크 #

개요 #

  • 2차원 배열에 대해 각각의 리스트의 합을 기준으로 정렬을 하고 그 순서를 반환하는 문제이다.
  • 파이썬에서는 내장함수 sort()를 사용하면 쉽게 풀 수 있다.

문제 해설 #

  • 입력으로 2차원 배열 mat과 출력값의 개수를 의미하는 정수 k가 주어진다.
  • mat에 있는 각각의 리스트는 0과 1의 조합으로 이루어져 있으며 1의 개수가 많은 리스트가 강한 리스트이다.
  • 문제에서 요구하는 것은 1. 리스트를 약한 순으로 정렬하고
    2. 정렬하기 전의 인덱스 번호를 정렬된 순서대로 반환하는 것이다.
  • 이를 위해 리스트의 인덱스 번호와 리스트의 합을 따로 저장할 필요가 있으므로 for문을 통해 mat을 순회한다.
  • 순회하면서 mat의 각 리스트 내용을 [인덱스 번호, 리스트의 합]으로 덮어쓰고
    이후에 1번 원소(리스트의 합)을 기준으로 mat를 정렬한다.
  • 마지막에 정렬된 mat의 0번 원소(인덱스 번호)를 k개 만큼만 추출해서 반환하면 된다.

해설 코드 #

python
class Solution(object):
    def kWeakestRows(self, mat, k):
        """
        :type mat: List[List[int]]
        :type k: int
        :rtype: List[int]
        """

        for i in range(len(mat)):
            mat[i] = [i, sum(mat[i])]

        mat.sort(key=lambda x: x[1])

        return [mat[i][0] for i in range(k)]