Daniel's blog

Computer Science를 공부한 사람이라면 익숙한 pid(process id)와 ppid(parent process id)의 개념이 담긴 문제다. 해당 문제에서 각 process는 1개의 parent process만을 가질 수 있고 반면에 parent process는 여러 child process를 가질 수 있다. 해당 문제의 예시 그림으론 Tree 형태로 제시가 됐고, kill을 하기 위한 pid가 input으로 주어지고, 해당 process를 비롯해 연쇄적으로 모든 child process를 kill을 하기 위해 필요한 모든 pid를 List의 형태로 반환하는 문제다. Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5 Output: [5,10] Exp..

아래와 같이 문자 다음 숫자로 이루어진 일종의 encoded string이 주어지고, 이에 따라 next()와 hasNext() 함수를 구현하는 문제다. next()와 hasNext() 함수를 구현하는 문제는 많이 출제되는 유형 중 하나다. Input: ["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"] [["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []] Output: [null, "L", "e", "e", "t", "C", "o", true, "d", true] class StringIterator: def __init__(self,..

같은 message가 10초 안에 다시 Print 되지 않도록 확인하는 함수를 만들면 된다. 파이썬의 해시맵을 사용해 해당 message의 timestamp를 확인하고 갱신해 True/False를 반환한다. class Logger: def __init__(self): self.d = defaultdict(int) def shouldPrintMessage(self, timestamp: int, message: str) -> bool: if message not in self.d: self.d[message] = timestamp return True else: if timestamp - self.d[message] < 10: return False else: self.d[message] = timestam..

A quadratic function(2차 함수)에 계수로 a와 b가 주어지고 y절편(y-intercept)으로 c가 주어지고, 정렬된 리스트(nums)가 주어진다. 이때 input에 따른 2차 함수의 output으로 이뤄진 리스트를 정렬해 반환해야된다. 이때 시간복잡도는 O(n)을 만족해야한다. 예시: Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5 Output: [3,9,15,33] 시간복잡도를 고려하지 않으면 간단한 정렬 알고리즘을 통해 O(n logn)의 시간복잡도로 정답을 얻을 수 있지만. O(n)의 시간복잡도를 만족하려면 주어진 리스트(nums)가 정렬됐다는 것과 2차 함수의 특징을 이용하면 된다. 2차 함수는 꼭지점을 중심으로 꼭지점으로부터의 x의 거리가 ..

이진 트리(binary tree)가 주어지고, 이진 트리의 노드(node)에서 각 노드의 val의 값이 1씩 증가하는 child로만 연결이 가능하고 가장 긴 path의 길이를 반환하면 된다. 재귀(Recursive)를 활용한 DFS(Depth First Search)로 풀었다. class Solution { private int M; public Solution() { M = 0; } private void dfs(TreeNode n, int cnt) { TreeNode l = n.left; TreeNode r = n.right; if (l != null) { if (n.val - l.val == -1) { dfs(l, cnt+1); } else { dfs(l, 1); } } if (r != null) ..

0과 1로 이뤄진 2차원 배열이 주어지고 1은 home을 의미한다. 모든 home으로의 거리 합이 최소인 지점(point)를 찾는 문제다. 거리는 Manhattan Distance를 활용한다. 제약 사항(constraint)에 의하면 2차원 배열의 최대 크기는 200(m) x 200(n)으로 크지 않기에 O (m x n)으로 풀이가 가능하지만, 더 효율적인 방법이 있을 것으로 생각된다. class Solution: def minTotalDistance(self, grid: List[List[int]]) -> int: m, n = len(grid[0]), len(grid) hL = [] for i in range(n): for j in range(m): if grid[i][j] == 1: hL.append..

Easy 문제로 설명과 예시는 아래와 같다. : Given a pattern and a string s, find if s follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Pattern과 String이 주어지고 주어진 String은 공백(space)를 통해 단어를 구분해뒀고, 각 단어를 하나의 문자로 치환했을 때 주어진 pattern과 일치가 가능하다면 true 그렇지 않으면 false를 반환하면 된다. Easy 문제임에도 acceptance rate는 41.7% 밖에 되지 않는다. Dictiona..

파티에 초대된 사람들의 정보가 리스트로 주어지고, 각 리스트의 요소는 그 사람이 다른 사람을 알고 있으면 1, 모르면 0으로 주어진다. 유명인사(Celebrity)는 다른 사람은 모두 모르지만 모든 사람이 그 사람을 알고있고, 그 사람은 오직 1명이거나 없다. 없으면 -1 있다면 그 사람의 인덱스를 반환하면 된다. Constraint의 n의 최대값이 100 밖에 되지 않아 3개의 반복문을 중첩(O(n))해 풀어 모든 테스트 케이스를 만족했지만, 효율적이진 않다. 효율적인 풀이는 O(n)으로도 가능한데 주어진 리스트의 0번부터 Celebrity 용의자를 추척하고(knows(celebrity, i)가 False 일 때까지), 용의자가 누군가 한 명이라도 알아 True을 반환하면 -1을 그렇지 않다면 해당 용..

class Solution: def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]: h = [] ret = [] def dfs(node): heapq.heappush(h, (abs(target-node.val), node.val)) if node.left != None: dfs(node.left) if node.right != None: dfs(node.right) dfs(root) for i in range(k): ret.append(heapq.heappop(h)[1]) return ret 270. Closest Binary Search Tree Value 문제의 고난이도 문제다. 이번엔 Target ..

Binary Search Tree의 root node와 Target value가 주어지고, Tree의 모든 node를 탐색해 Target value의 가장 근사한 value를 가진 node를 return하면 된다. DFS를 통해 left child와 right child가 존재하면 계속 탐색해 나가는 방식으로 구현했다. class Solution: def closestValue(self, root: Optional[TreeNode], target: float) -> int: def dfs(node, target): l = r = math.inf if node.left != None: l = abs(node.left.val - target) if node.right != None: r = abs(node...