Daniel's blog

n이라는 input이 주어졌고 이는 계단의 높이로 계단은 한 번에 한 개 혹은 두 개를 오를 수 있고, 가장 높은 계단에 오를 수 있는 경우의 수를 구하는 것이다. 아래 제공된 솔루션은 한 개와 두 개를 오를 때 필요한 개수를 조합해 각 개수에 따른 경우의 수(number of cases)를 구해 하나씩 더해 나가는 것이다. You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?. Example 1: Input: n = 2 Output: 2 Explanation: There..

굉장히 기초적인 문제다. 주어진 배열(nums)에서 target으로 주어지는 숫자의 개수가 과반을 넘으면 True 넘지 못하면 False를 반환하는 문제다. class Solution: def isMajorityElement(self, nums: List[int], target: int) -> bool: dic = defaultdict(int) for i, n in enumerate(nums): dic[n] += 1 if dic[target] * 2 > len(nums): return True else: return False

Worker의 2차원 좌표를 담은 workers와 Bike의 2차원 좌표를 담은 bikes 리스트가 각각 주어지고, worker와 bike가 가장 가깝게 쌍을 지어주는 문제다. 문제를 복잡하게 생각해 Priority Queue(우선순위 큐)를 사용하기 위해 heapq를 사용했으나 오히려 사이즈가 큰 input은 TLE(Time Limit Exeeded)가 발생한다. 오히려 간단하게 거리를 계산한 모든 쌍을 리스트에 담고 리스트를 정렬해 거리가 짧은 순서부터 반환할 리스트에 담으면 쉽게 해결된다. 아래는 앞서 말한 모든 쌍을 리스트에 담고 정렬한 솔루션인데 시간복잡도 측면에선 중복 체크를 리스트(bl) 대신 세트를 사용하면 훨씬 개선이 가능하다. 참고로 가장 높은 vote를 받은 솔루션은 Bucket So..

String과 words List가 input으로 주어지고, 주어진 words List의 substring이 s에 존재한다면 html의 bold tag()를 앞뒤로 씌워 return 하는 문제다. Input: s = "abcxyz123", words = ["abc","123"] Output: "abcxyz123" Explanation: The two strings of words are substrings of s as following: "abcxyz123". We add before each substring and after each substring. 이 문제 역시 다양한 Data Structure와 Algorithm을 활용해 풀 수 있겠지만, Min Heap을 사용해 풀었다. Min Heap은 ..

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..