목록algorithm (7)
서랍장
class Solution: def maximizeSweetness(self, sweetness: List[int], k: int) -> int: # Initialize the left and right boundaries. # left = 1 and right = (total sweetness) / (number of people). number_of_people = k + 1 left = min(sweetness) right = sum(sweetness) // number_of_people while left < right: mid = (left + right + 1) // 2 cur_sweetness = 0 people_with_chocolate = 0 # Start assigning chunks ..
1060. Missing Element in Sorted Array n = [1, 2, 4], k = 3일 때를 생각해보면 좋다. class Solution: def missingElement(self, nums: List[int], k: int) -> int: missing = lambda idx: nums[idx] - nums[0] - idx n = len(nums) # for the case [1, 2, 4] # 4 + 3 - 1 = 6 if k > missing(n-1): return nums[-1] + k - missing(n-1) idx = 1 while missing(idx) < k: idx += 1 return nums[idx-1] + k - missing(idx-1) binary sera..
1662. Check If Two String Arrays are Equivalent 매우 간단한 문제다. class Solution: def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool: mergedWord1 = ''.join(word1) mergedWord2 = ''.join(word2) return mergedWord1 == mergedWord2
Rotate Array, 문제는 정말 간단하다. 그렇지만 시간복잡도를 O(1)으로 풀기 위해서는 약간의 아이디어가 필요한데, 배열의 item 값을 바꿀 때, item을 가르키는 prev을 지정해야하고, cnt로 전체 item을 탐색하고 있는지 추적해야한다. start는 n//k값이다. class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) k %= n # start defines start = cnt = 0 while cnt < n: # prev는 바뀌기 이전의 value를 지정 curr, prev = st..
1239. Maximum Length of a Concatenated String with Unique Characters backtracking이랑, 이중 for문 2가지로 해결할 수 있다. 1. 백트래킹 class Solution: def maxLength(self, arr: List[str]) -> int: self.maxLength = 0 # s is 현재까지의 문자열 # 탐색하는 문자열의 idx def backtrack(s, j): if len(s) != len(set(s)): return self.maxLength = max(len(s), self.maxLength) for idx in range(j, len(arr)): backtrack(s + arr[idx], idx) backtrack('..
요새 코테 공부를 다시 매일 한 문제 씩 풀어나가고 있다. 프로그래머스 이분 탐색 문제도 풀면서, while l bool: pass # could be [0, n], [1, n] etc. depends on problem left, right = min(searchSpace), max(searchSpace) while left < right: mid = left + (right - left) // 2 if condition(mid): right = mid else: left = mid..
import sys import heapq def dijk(v, r, x): r[x-1] = 0 que = [] heapq.heappush(que, (r[x-1], r.index(r[x-1]))) while que: vertex, index = heapq.heappop(que) if r[index] = weight: r[x-1] = weight heapq.heappush(que, (r[x-1], x-1)) input = sys.stdin.readline INF = sys.maxsize N, M, X = map(int, input().split()) ..
