Daniel's blog

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

266번 문제와 유사하다. 266번은 가능한지 불가능한지만을 true, false로 반환하면 되지만 여기서 불가능하면 깡통([])을 반환하고, true면 구성 가능한 모든 String을 반환하는 것이다. 우선 false의 경우는 266번과 같은 방식을 활용하면 되고, dfs를 통해 String을 구성해 반환하면 된다. class Solution: def __init__(self): self.palL = [] def form(self, even, pal): if len(even) == 0: self.palL.append(pal) return for i in range(len(even)): cur = even[i] copyE = even.copy() copyE.remove(cur) self.form(copy..

주어진 String의 character의 위치만 변경(permutation)해 palindrome이 가능하다면 true 불가능하면 false를 반환하는 문제다. 난이도는 Easy로 아이디어는 매우 간단하다. palindrome의 조건은 String을 앞에서 읽었을 때와 뒤에서 읽었을 때 같은 것으로, String을 구성하는 character의 종류가 모두 짝수거나 한 가지만 홀수를 가질 수 있다. 예를 들어, "aabb"는 palindrome이 되기 위해선 "abba", 혹은 "baab"가 되면 되고 이는 'a' 또는 'b'의 위치 변경을 통해 구성이 가능하고 'a'와 'b'의 개수가 각 2개씩으로 모두 짝수다. "ccbba" 역시 1개(홀수개)인 'a'를 중앙에 위치시켜 "cbabc" 혹은 "bcacb..

157. Read N Characters Given read4의 연장선에 있는 문제로 이 문제 역시 비추천이(1.7K)로 추천(840)을 압도한다. 157번 문제와 다른 점은 완성해야되는 read() 함수가 여러번 불리는 것이다. 그렇기에 이전에 파일의 어디까지 읽었는지를 따로 저장하는 prevI라는 변수와 이전에 파일에서 읽어왔지만 4개까지만 반환이 가능해 아직 반환하지 못했던 내용을 저장해두고 다음에 read() 함수가 호출될 때 전달해주기 위한 버퍼인 prevB 버퍼를 추가하는 것이 핵심이다. 이번엔 Java로 풀어봤다. public class Solution extends Reader4 { /** * @param buf Destination buffer * @param n Number of cha..

문제 설명은 아래와 같다. : Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters. Method read4: The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4. The return value is the number of actual characters read. Note that read4() has its own file pointer, much like FILE *fp in C...

문제 설명은 아래와 같다. : There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by an n x k cost matrix costs. For example, costs[0][0] is the cost of paintin..

난이도는 Easy로 아래와 같다. Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10). All messages will come in chronological order. Several messages may arrive at the same timestamp. Imple..