거누의 개발노트

문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. 예제 입력 9 0 12345678 1 2 0 0 0 0 32 예..

문제 정수 배열 nums이 주어지면 배열에서 k번째로 가장 큰 요소를 반환 하는 프로그램을 작성하시오. 입력 Input: nums = [3,2,1,5,6,4], k = 2 출력 Output: 5 작성한 코드1 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: return heapq.nlargest(k,nums)[-1] https://leetcode.com/problems/kth-largest-element-in-an-array/ Kth Largest Element in an Array - LeetCode Level up your coding skills and quickly land a job. This is the be..

문제 m x n이진 행렬 mat이 제공 되는데, 1의 개수가 가장 적은 k 개의 인덱스를 반환하는 프로그램을 작성하시오. 입력 Input: mat = [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]], k = 3 출력 Output: [2,0,3] 작성한 코드1 def kWeakestRows(mat: List[List[int]], k: int) -> List[int]: ans = [] s = collections.defaultdict(int) for i in range(len(mat)): # 1의 개수가 몇 개인지 c = collections.Counter(mat[i]) # 인덱스를 키로 1의 개수 만큼으로 하는 딕셔너리 s[i] = c[..

문제 정수 배열에서 (첫번째 최대값-1)*(두번째 최대값-1)을 해주는 프로그램을 작성. 입력 Input: nums = [3,4,5,2] 출력 Output: 12 # (5-1)*(4-1) 작성한 코드1 def maxProduct(nums: List[int]) -> int: n = sorted(nums, reverse=True) return (n[0]-1)*(n[1]-1) 작성한 코드2 def maxProduct2(nums: List[int]) -> int: h = heapq.nlargest(2, nums) return (h[0] - 1) * (h[1] - 1) list를 sort 할 때 는 시간 복잡도가 O(NlogN) 이고, heapq는 push, pop 할 때 O(logN) 이여서 힙이 빠르다는걸 알..

문제 이진 트리를 직렬화 및 역직렬화하는 알고리즘을 설계합니다. 직렬화/역직렬화 알고리즘이 작동하는 방식에는 제한이 없습니다. 이진 트리를 문자열로 직렬화할 수 있고 이 문자열을 원래 트리 구조로 역직렬화할 수 있는지 확인하기만 하면 됩니다. 입력 Input: root = [1,2,3,null,null,4,5] 출력 Output: [1,2,3,null,null,4,5] 작성한 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): q..

문제 이진 트리가 주어지면 root트리를 반전 하고 루트 를 반환합니다. 입력 root = [4,2,7,1,3,6,9] 출력 [4,7,2,9,6,3,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 def list_to_tree(lst, idx): parent = None if idx < len(lst): value = lst[idx] if value is not None: parent = TreeNode(value) parent.left = list_to_tree..

문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 Input: root = [5,4,5,1,1,5] 출력 Output: 2 처음에 지나온 노드의 개수 인줄 알고 엥? 왜 2개이지 한참 고민했다. 출력을 다시 생각해보니 간선의 개수였다... 아무튼 이 문제도 처음 접근하는 나에게는 어려운 친구들이었다. 역시 그냥은 잘 안 풀려서 책에 도움을 받았다. 뭐 어떤가..잘 이해해서 내걸로 만들면되지! def longestUnivaluePath(root) -> int: rtn = [0] def dfs(node:TreeNode): if node is None: return 0 #왼쪽 노드 값도 구해와 줄래? left = dfs(node.left) #오른쪽 노드 값도 구해와 줄래? right = dfs(node.r..

문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 입력 TreeNode [1,2,3,4,5] 출력 3 먼저 내 코드에서 테스트 해보려면 배열을 리스트로 만드는 과정이 필요했다. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def make_tree_by(lst, idx): parent = None if idx < len(lst): value = lst[idx] if value == None: return parent = TreeNode(value) parent.left = make_tree_by(lst, 2 * idx + 1) ..