Daniel's blog

전형적인 Union-Find를 활용하는 문제다. 다만 Cycle이 발생할 수 있기에 이 때(if px == py) false를 반환하는 조건만 추가해주고 Parent가 하나라도 다르다면 Tree가 두 개 이상 생기는 것이기에 false를 반환하면 된다. class Solution: def find(self, p, x): if p[x] == x: return x return self.find(p, p[x]) def union(self, p, x, y): x = self.find(p, x) y = self.find(p, y) if x bool: p = [i f..

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

https://leetcode.com/problems/3sum/ LeetCode 13번 3Sum 문제는 다음과 같다. Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Constraints: 3