Daniel's blog

createPath 함수에 주어지는 input 중 하나인 path를 '/'로 split해 parent path와 비교해가며 함수를 완성하려 했지만, Test case에 번번히 걸려 다른 방법으로 풀었다. split을 통해 '/'로 path를 자르는건 동일하지만 split 된 list에서 마지막 요소만 제외하고 하나의 String으로 다시 구성해 parent에 대한 True/False를 확인하는 방식으로 풀었다. get 함수는 Hash map을 통해 수월하게 구현했다. class FileSystem: def __init__(self): self.p = {} def createPath(self, path: str, value: int) -> bool: if path in self.p: return False..

알파벳 26개로 구성된 keyboard String이 input으로 주어지고 0부터 25까지를 개개의 index로 간주하고, Hash map의 key로 keyboard의 각 character를 value로 넣은 후, 또 다른 input인 word의 character를 앞에서 하나씩 읽어들여 각각을 Hash map의 key로서 value를 찾는다. 그리고 차이(절대값)의 누적합을 반환했다. class Solution: def calculateTime(self, keyboard: str, word: str) -> int: dic = {} p = 0 ret = 0 for i, k in enumerate(keyboard): dic[k] = i for i, w in enumerate(word): ret += ab..

class Solution: def minSwaps(self, data: List[int]) -> int: ret = ones = 0 for i, d in enumerate(data): if d == 1: ones += 1 for i in range(ones): if data[i] == 0: ret += 1 cnt = ret for i in range(ones, len(data)): if data[i-ones] == 0: cnt -= 1 if data[i] == 0: cnt += 1 ret = min(ret, cnt) return ret 0과 1로 이뤄진 'data'라는 binary array가 input으로 주어질 때 모든 1이 연속하도록 그룹을 지을 때 최소로 swap하는 수를 반환하는 문제다. Tw..

Input으로 주어진 s가 또 다른 input인 t의 subsequence(연속이 아니더라도 포함이 돼있다면)인지 True/False를 반환하면 된다. 순서를 지켜야하기 때문에 sorting이나 hash map을 사용하는 것이 아니라 index를 이용해 비교해 나가는 방식으로 풀었다. Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing t..

'169. Majority Element'에서 난이도가 조금 올라간 문제지만 큰 틀에선 똑같기에 솔루션 역시 흡사하다. Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. Example 1: Input: nums = [3,2,3] Output: [3] Example 2: Input: nums = [1] Output: [1] class Solution: def majorityElement(self, nums: List[int]) -> List[int]: dic = defaultdict(int) for i, n in enumerate(nums): dic[n] += 1 ret = [] for i, k i..

1150번과 매우 유사한 문제다. 다만 다른 점은 해당 문제에선 Majority Element가 반드시 있다는 가정하에 이를 반환하는 것이고, 1150은 input으로 주어진 숫자가 Majority Element가 맞는지 틀린지를 반환하는 것이다. Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1: Input: nums = [3,2,3] Output: 3 Example 2: In..

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