pjaehyun의 개발일지

문제

https://leetcode.com/problems/median-of-two-sorted-arrays/

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

1. 배열 nums1과 배열 nums2가 주어질 때 두 배열의 중간값을 반환하라.

2. 시간복잡도는 O(log(m+n))

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1.extend(nums2)
        merge = sorted(nums1)
        if len(merge) % 2 == 0:
            mid1, mid2 = len(merge) // 2 - 1, len(merge) // 2
            return (merge[mid1] + merge[mid2]) / 2
        else:
            mid = len(merge) // 2
            return float(merge[mid])

1. nums1과 nums2의 중간값을 구하기위해 nums1과 nums2를 합쳐준다

  - 방법1. nums1.extend(nums2)

  - 방법2. nums1 + nums2(파이썬은 배열두개를 더하면 합쳐진다.)

  - 방법3. heapq.merge를 이용하는 방법 등 여러가지 방법이 존재한다

2. 합쳐진 nums1을 정렬해주고 중간값을 구한다.

3. merge의 길이가 짝수일 때 중간에 해당하는 두개의 값을 더하고 2로 나눈값을 반환한다.

4. merge의 길이가 홀수일 때 중간값을 반환한다.

문제

https://leetcode.com/problems/3sum-closest/

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

1. 정수로 이루어진 배열nums와 target이 주어질 때 세개의 정수의 합계가 target에 가장 가까운 값을 찾아라

2. 세개의 정수의 합을 반환해라

3. 각 입력에는 하나의 솔루션만 존재한다

Example 1:

Example 2:

Constraints:

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

문제풀이 코드

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        _min = 100000

        for idx, num in enumerate(nums):
            left = idx + 1
            right = len(nums) - 1

            while left < right:
                _sum = num + nums[left] + nums[right]
                if abs(target - _sum) < abs(target - _min):
                    _min = _sum
                
                if _sum > target:
                    right -= 1
                else:
                    left += 1
        return _min

투포인터 방식으로 문제 접근

1. enumerate를 통해 index와 값을 가져온다.

2. left는 현재 값의 index + 1, right는 배열의 마지막 index값으로 초기화 한다.

3. left가 right와 크거나 같을 때까지 반복문을 돌려준다

4. 현재값인 num과 nums[left], nums[right] 세개의 숫자를 합한다.

5. abs(target - _sum) < abs(target - _min) 일 때 _min값을 _sum값으로 바꿔준다. (절대값으로 비교하는건 거리를 비교하기 때문)

6. _sum값이 target보다 크면 right를 - 1해주고 반대의 경우 left를 + 1 해준다.

문제

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

BST에서 두개의 요소가 target이랑 값이 같으면 true, 아니면 false를 반환하라

Example 1:

Example 2:

문제풀이 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        lst = []
        return dfs(root, lst, k)

def dfs(root, lst, val):
    if not root:
        return False
    
    if (val - root.val) in lst:
        return True
    
    lst.append(root.val)
    return dfs(root.left, lst, val) or dfs(root.right, lst, val)

dfs로 접근하여 문제 풀이

1. root가 None일 때는 False를 리턴하고

2. val -  root.val이 lst안에 있다면 True를 반환(root.val + lst안에 어떤 값 = val)

3. lst에 root.val을 넣어주면서 dfs를 호출하여 비교 

•    return A or B => A 와 B둘다 참일 때 A를 반환
•    return A or B => A 와 B둘다 거짓일 때 B를 반환
•    return A or B => A와 B 중 하나만 참일 때 참인값을 반환

문제

https://leetcode.com/problems/add-one-row-to-tree/description/

Given the root of a binary tree and two integers val and depth, add a row of nodes with value val at the given depth depth.

Note that the root node is at depth 1.

The adding rule is:

• Given the integer depth, for each not null tree node cur at the depth depth - 1, create two tree nodes with value val as cur's left subtree root and right subtree root.
• cur's original left subtree should be the left subtree of the new left subtree root.
• cur's original right subtree should be the right subtree of the new right subtree root.
• If depth == 1 that means there is no depth depth - 1 at all, then create a tree node with value val as the new root of the whole original tree, and the original tree is the new root's left subtree.

Example 1:

Example 2:

문제풀이 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        if depth == 1:
            return TreeNode(val, left=root)
        
        level = 1
        queue = deque([root])

        while queue:
            level += 1
            for i in range(len(queue)):
                current = queue.popleft()
                
                if level == depth:
                    current.left = TreeNode(val, left=current.left)
                    current.right = TreeNode(val, right=current.right)
                
                else:
                    queue.append(current.left) if current.left else None
                    queue.append(current.right) if current.right else None
        
        return root if depth > 1 else TreeNode(val, left=root)

트리 삽입으로 접근하여 문제풀이

1. level이 depth까지 도달하지 않았다면 점점 트리를 아래쪽으로 탐색

2. level이 depth가 아니라면 큐에 현재 노드의 left노드와 right노드를 삽입

3. level이 depth와 같다면 현재 위치에 val을 삽입한다

4. depth가 1보다 작다면 노드가 하나만 존재하기때문에 새로운 노드에 root노드를 연결하여 반환한다

문제

https://leetcode.com/problems/path-sum/

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

이진트리 root와 정수 targetSum이 주어지면, 루트노드 - 리프노드까지의 합이 targetSum과 같으면 true를 반환해라.

리프노드는 자식이 없는 노드이다.

Example 1:

문제풀이 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
result = []
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        global result
        preOrder(root, targetSum)
        
        if targetSum in result:
            result.clear()
            return True
        else:
            result.clear()
            return False

def preOrder(root, target):
    global result
    if root == None:
        return
    
    if root.left == None and root.right == None and target == root.val:
        result.append(root.val)

    if root.left != None:
        root.left.val += root.val
    preOrder(root.left, target)

    if root.right != None:
        root.right.val += root.val
    preOrder(root.right, target)

트리 전위 순회 방식으로 문제 해결(전위 순회는 깊이 우선 순회라고도 함)

1. 루트 노드에서 출발하여 자식노드가 존재할 때 루트노드의 val값을 자식노드의 val값에 더한 뒤 자식노드로 전위순회를 호출한다

2. 노드의 left, right가 둘 다 None이라면 리프노드이기 때문에 해당 val값을 결과에 담아준다

3. preOrder가 종료되면 result안에 targetSum이 있는지 체크하여 결과값을 반환한다

** result를 global로 호출하여 clear()해주지 않으면 통과가 되지않았다... 정확도 깎아먹음

    해결 후 다른사람의 풀이를 봤는데 class를 실행할 때 __init__에 초기값을 세팅해주는 사람도 있었다.. :)

문제

https://leetcode.com/problems/decode-ways/

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

인코딩된 메세지를 디코딩하여 디코딩할 있는 방법의 수를 리턴해라.

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0 for _ in range(len(s) + 1)]
        dp[0], dp[1] = 1, 1

        if s[0] == '0' or len(s) <= 0: return 0

        for i in range(1, len(s)):
            if s[i] != '0':
                dp[i + 1] = dp[i + 1] + dp[i]
            if s[i - 1] != '0' and 1 <= int(s[i-1:i+1]) <= 26:
                dp[i + 1] = dp[i + 1] + dp[i - 1]
        return dp[len(s)]

dp로 문제 접근

1. dp[i + 1] = dp[i+1] + dp[i]는 s[i]가 0이 아닐 때 성립하고

2. dp[i + 1] = dp[i+1] + dp[i-1]는 s[i-1]이 0이 아니고 s[i-1]과 s[i]을 합쳤을 때 1보다 크거나 같고 26보다 작거나 같을 때 성립한다.

3. 위 조건대로 구현하여 dp배열에서 배열 s의 길이번째 값을 리턴한다.

문제

https://leetcode.com/problems/find-k-closest-elements/description/

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

정렬된 정수 배열 arr이 주어지고 정수 k, x가 주어질 때, 정수 x에서 가장 가까운 원소를 k개만큼 배열에 담아 오름차순으로 정렬하여 반환한다.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr) - k
        while left < right:
            mid = (left + right) // 2
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        return arr[left:left + k]

투 포인터 방식으로 문제를 접근하였다

1. left = 0, right = 배열의 길이 - k로 두개의 포인터를 만들어준다

2. 두개의 포인터의 mid를 구한다.

3. x - arr[mid]와 arr[mid + k]값을 비교한다.

4. x - arr[mid]이 arr[mid + k]보다 크면 left = mid + 1

5. x - arr[mid]이 arr[mid + k]보다 작으면 right = mid

6. left 와 right가 같으면 루프를 종료하고 arr[left:left+k]를 리턴해준다. 

문제

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Given the head of a linked list, remove the nth node from the end of the list and return its head.

링크드리스트가 주어지면 뒤에서 n번째에 있는 요소를 지우로 리턴하라

Example 1:

Example 2:

문제풀이 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        lst = nodeToList(head)
        lst.pop(len(lst) - n)
        if len(lst) <= 0:
            return
        listNode = ListNode(lst[0])
        
        for i in range(1, len(lst)):
            listNode = makeNode(listNode, lst[i])
        return listNode

def nodeToList(listNode):
    lst = []
    node = listNode
    while True:
        if node == None:
            return lst
        lst.append(node.val)
        node = node.next
        
def makeNode(listNode, n):
    if listNode == None:
        return ListNode(n)
    else:
        listNode.next = makeNode(listNode.next, n)
    return listNode

1. 주어진 링크드리스트의 모든 val값을 추출하여 리스트로 변환

2. 해당 리스트에서 뒤에서 n번째에 있는 요소를 제거한다

3. 리스트에 들어있는 값들로 다시 링크드리스트를 생성하고 리턴한다